Caching is a technology that can improve data read performance, such as CPU cache, database cache, browser cache, etc.

2. The size of the cache is limited, when the cache space is used up, which data should be cleared out, which data should be retained? This is a decision that requires a cache elimination strategy. Here are some of the things I learned:

  • Rough FIFO (First In, First Out) you can use browser-like max-age here, or simply queue push,shift.
  • LFU (Least Frequently Used)
  • LRU (Least Recently Used)

3. The core idea is: “If the data has been accessed recently, then the probability of being accessed in the future is higher.”

Insert elements in the header using arrays requires a lot of steps and poor performance, so a linked list is used to implement the React Fiber traversal idea. First we need to implement a fully functional linked list:

  function NodeList () {
    this.head = new Node("head")
    this.length = 0 // List length
  }
  NodeList.prototype.findNode = function (item) {
    let curNode = this.head
    while(curNode.data ! == item) { curNode = curNode.next }return curNode
  }

  NodeList.prototype.deleteNode = function (item) {
    let curNode = this.head
    while(curNode.next ! = =null& curNode.next.data ! == item) { curNode = curNode.next }if(curNode.next ! = =null) {
      curNode.next = curNode.next.next
    }
  }

  NodeList.prototype.insertNode = function (newData, data) {
    const newNode = new Node(newData)
    const findNode = this.findNode(data)
    newNode.next = findNode.next
    findNode.next = newNode
    this.length++
  }

  NodeList.prototype.consoleDisplay = function () {
    let curNode = this.head
    let num = 0
    while(curNode.next ! = =null) {
      num++
      console.log(num + '. ', curNode.next.data)
      curNode = curNode.next
    }
  }

  function Node (data) {
    this.data = data
    this.next = null
  }

  const nodelist = new NodeList()
  console.log('list', nodelist)
  nodelist.insertNode("Name".'head')
  nodelist.insertNode("Gender".'name')
  nodelist.insertNode("年龄 ".'gender')

  // See how the list is arranged
  nodelist.consoleDisplay()
  NodeList {head: Node {data: 'head', next: null}, length: 0} * 1. Name * 2. Gender * 3. Age **/
Copy the code

With the linked list, we will sort out the process of LRU cache.

  1. If the data exists in the list, iterate to get the node, remove it from its original position, and add it to the head of the list.
  2. If the data does not exist in the linked list, there are two possibilities:
  • If the cache is not full, add new data directly to the head of the list.
  • The cache is full, the tail node is removed, and new data is added to the head of the list
  • Directly on the code, first declare an LRU cache class, and update the cache space method
  function LRUCache(maxSpace) {
  this.nodelist = new NodeList()
  this.cacheSpace = this.nodelist.length
  this.maxSpace = maxSpace
}
LRUCache.prototype.updateSpace = function () {
  this.cacheSpace = this.nodelist.length
  return this
}
Copy the code
  • You then define the cache method cacheNode to enter the new content
LRUCache.prototype.cacheNode = function (item) {
  if (this.nodelist.findNode(item) ! = =null) {
    // 1. If the data exists in the list, iterate to get the node, remove it from its original position, and add it to the head of the list.
    this.nodelist.deleteNode(item).insertNode(item, 'head')}else {
    // 2. If the data does not exist in the linked list, there are two possibilities:
    if (this.cacheSpace < this.maxSpace) {
      If the cache is not full, add new data directly to the head of the list.
      this.nodelist.insertNode(item, 'head')}else {
      If the cache is full, delete the tail node and add new data to the head of the list
      console.log("Cache full, automatically delete the least visited.")
      this.deleteLast().insertNode(item, 'head')}}// Update the cache space
  this.updateSpace()
  return this
}
Copy the code
  • When we run out of cache space, we need to remove the end of the list
LRUCache.prototype.deleteLast = function () { let curNode = this.nodelist.head let preNode = null while(curNode.next ! == null && curNode.next.data ! == null) { preNode = curNode curNode = curNode.next } console.log(JSON.stringify(preNode), Prenode. next = null return this.nodelist}Copy the code
  • Finally, define a method to print the cached contents
LRUCache. Prototype. Display = function () {the console. The log (' biggest cache space + enclosing maxSpace + 'a') enclosing nodelist. ConsoleDisplay ()} Const cache_LRU = new LRUCache(10) // Up to 10 list entitiesCopy the code

Five. Ha ha, the code is done, we are looking forward to the verification link

  1. Enter the name first and see the print result. The name has been cached in, and the maximum cache space is printed
  cache_LRU.cacheNode("Name")
  cache_LRU.display() 
  // The maximum cache space is 10
  / / 1. Name
Copy the code
  1. Enter gender and it comes before the name
  cache_LRU.cacheNode("Name")
  cache_LRU.cacheNode("Gender")
  cache_LRU.display()
  // The maximum cache space is 10
  / / 1. Gender
  / / 2. The name
Copy the code
  1. Age is replaced at the head of the list, followed by gender, and then name
  cache_LRU.cacheNode("Name")
  cache_LRU.cacheNode("Gender")
  cache_LRU.cacheNode("Age")
  cache_LRU.display() 
  // The maximum cache space is 10
  / / 1. Age
  / / (2) gender
  / / 3. The name
Copy the code
  1. Type in an existing name and see if the name will be reloaded to the header to make it Least Recently Used.
  cache_LRU.cacheNode("Name one")
  cache_LRU.cacheNode("Name 2")
  cache_LRU.cacheNode("Name 3")
  cache_LRU.cacheNode(4 "name")
  cache_LRU.cacheNode(Name five "")
  cache_LRU.cacheNode(6 "name")
  cache_LRU.cacheNode(7 "name")
  cache_LRU.cacheNode("Name")
  cache_LRU.cacheNode("Name nine")
  cache_LRU.cacheNode(10 "name")
  cache_LRU.cacheNode(11 "name")
  cache_LRU.display()
  // The maximum cache space is 10
  / / 1. Name
  / / 2. Age
  / / 3. Gender
Copy the code
  1. The last step is to verify that when the cache is full, the least frequently used ones are eliminated. It is found that name 1 has been eliminated from the cache, and the last entered name 11 is the first
  cache_LRU.cacheNode("Name one")
  cache_LRU.cacheNode("Name 2")
  cache_LRU.cacheNode("Name 3")
  cache_LRU.cacheNode(4 "name")
  cache_LRU.cacheNode(Name five "")
  cache_LRU.cacheNode(6 "name")
  cache_LRU.cacheNode(7 "name")
  cache_LRU.cacheNode("Name")
  cache_LRU.cacheNode("Name nine")
  cache_LRU.cacheNode(10 "name")
  cache_LRU.cacheNode(11 "name")
  cache_LRU.display() 
  // The maximum cache space is 10
  // 1. Name 11
  // 2
  // 3
  // 4
  // 5
  // 6
  // 5
  // 8
  // 9
  // name 2
Copy the code