What is the LRU

LRU (Least Recently Used) refers to the Least Recently Used cache. The front-end often uses the cache during performance optimization to achieve the performance optimization goal by exchanging space for time.

The most commonly used cache library is LRU-cache. The front-end SSR framework NUXT uses LRU-cache to realize the functions of page cache, component cache and interface cache, so as to reduce the load of server CPU and improve the concurrent number of SSR pages.

LRU implementation

Let’s take a look at what LRU needs to achieve.

  1. Need to be given the length of a data structure, can not be unlimited cache data;
  2. The LRU instance provides a get method to retrieve data from the cache using the key, or -1 if none is present.
  3. An LRU instance provides a PUT method that changes the value of the data, modifies it if it exists, inserts a new data if it does not exist, and removes the oldest unused keyword when the length of the data is exceeded.
  4. Time complexity of GET and PUT must be O(1).

Selection of basic data structure

Problem a

For a good front-end engineer, it is easy to implement 1, 2, and 3 with pure arrays, but not with time complexity. With arrays, both get and PUT have O(n) time complexity.

I’m not going to expand the implementation of arrays here, but why is it O(n) time and look at my other paper linear tables

Therefore, in order to realize the operation of the storage structure, the storage of the cache data is selected here.

Question 2

A new problem appears after the selection of bidirectional linked list. As we all know, the time complexity of the insertion and deletion of the list is O(1), but the time complexity of the search of the list is O(n), so the query operation must be used in the implementation of GET.

To address the time complexity of queries, Map data structures are a natural choice. Es6 Map data structure is the query time complexity is exactly O(1).

Why not just use objects instead of maps? In fact, the use of objects here can also achieve some simple requirements, if the key is a string or string, just need to transform the operation, can also achieve the requirements. However, more complex scenarios with key types are required, and LRU requirements cannot be met when using objects directly

Here, LRU is realized through the combination of bidirectional linked list and Map data structure. Bidirectional linked list is used to store data and Map is used to mark the location of key in the list. Thus, it is easy to realize the data structure of LRUCache.

Because to achieve O(1) time complexity, the first thing that comes to mind is to use THE Map data structure of ES6.

Simply implement it in Typescript

class LinkNode {
  key: number
  value: number
  _prev: LinkNode | null
  _next: LinkNode | null
  constructor(key: number, val: number) {
    this.key = key
    this.value = val
    this._prev = null
    this._next = null}}class LRUCache {
  head: LinkNode | null
  tail: LinkNode | null
  size: number
  map: Map<number, LinkNode>
  constructor(capacity: number) {
    this.size = capacity
    this.map = new Map(a)this.head = null
    this.tail = null
  }

  get(key: number) :number {
    // Check the map to see if the data exists
    if (this.map.has(key)) {
      let node = this.map.get(key) as LinkNode
      let _prev = node._prev
      let _next = node._next

      If it is a head node, it does not need to do any operation on the linked list. If it is a head node, it needs to operate on the chain expression to the nearest cache
      if (_prev) {
        // There is no need to move the node to the head node

        // The current node is the tail node
        if(! _next) {this.tail = _prev
        } else {
          _next._prev = _prev // Equivalent to node._next-_prev = node._prev
        }

        // 1. Remove a node from a linked list
        _prev._next = _next // Equivalent to node._prev._next = node._next

        // 2. Place node at the head of the list
        node._prev = null

        if (this.head) {
          node._next = this.head
          this.head._prev = node
        }
        this.head = node
      }

      // Returns the desired data value
      return node.value
    }

    return -1
  }

  put(key: number.value: number) :void {
    // The PUT function consists of two parts: modification and addition

    if (this.map.has(key)) {
      / / modify
      let node = this.map.get(key) as LinkNode
      node.value = value
      let _prev = node._prev
      let _next = node._next

      if (_prev) {
        if(! _next) {this.tail = _prev
        } else {
          _next._prev = _prev // Equivalent to node._next-_prev = node._prev
        }

        // The non-header section needs to lift the node to the head of the list
        _prev._next = _next
        node._next = this.head
        node._prev = null
        this.head && (this.head._prev = node)
        this.head = node
      }
    } else {
      let node = new LinkNode(key, value)
      this.map.set(key, node)

      if (this.head) {
        node._next = this.head
        this.head._prev = node
        this.head = node
      } else {
        this.head = this.tail = node
      }

      // New data scenario
      if (this.map.size > this.size) {
        let _tail = this.tail as LinkNode
        this.map.delete(_tail.key)

        this.tail = _tail._prev

        if (this.tail) {
          this.tail._next = null
        }

        if (this.head.key === _tail.key) {
          this.head = null
        }
      }
    }
  }
}
Copy the code