Three ways to implement LRU cache (recommended Collection)

Keep creating , Accelerate growth ！ This is my participation 「 Nuggets day new plan · 6 Yuegengwen challenge 」 Of the 28 God , Click to see the event details

LRU Its full name is Least Recently Used, I.e. recently used . It is aimed at the limited memory space , Cache only the most recently used data （ namely get and set The data of ）, Data exceeding the limited memory space will be deleted . This is often asked in the interview questions , Next, let's see how to implement .

analysis

By definition ,LRU There are at least two features ： Read and write through key value pairs 、 Orderly . Read and write key value pairs , Generally, we will use a hash table to represent , Note that the hash table is a logical structure , Actually we need to use object、map And so on to achieve ; Data order , That is, the most recently used data is placed in the front , Outdated data is put behind or deleted , And support that the data is sortable , We can think of arrays 、 Linked list 、map Data formats such as . therefore , We have three ways to achieve LRU cache ：

• Map
• Object + Array
• DoublyLinkedList

Use Map Realization LRU cache

Map Objects hold key value pairs , And you can remember the original insertion order of the keys .

const map = new Map();
map.set(2, 2);
map.set(1, 2);
console.log(map); // Map(2) {2 => 2, 1 => 2}, In the original insertion order 
const obj = new Object();
obj[2] = 2;
obj[1] = 1
console.log(obj); // {1: 1, 2: 2}, Not in the original insertion order 

Then we can base on Map Feature implementation LRU, Here is the schematic diagram ：

Implementation code ：

class LRUCache {
    data = new Map(); //  data map
    constructor(length) {
    if (length < 1) throw new Error(' The length cannot be less than 1')
        this.length = length
    }

    set(key, value) {
        const data = this.data;
        //  If the object exists , Then delete 
        if (data.has(key)) {
            data.delete(key);
        }
        //  Add data objects to map in 
        data.set(key, value);
        if (data.size > this.length) {
            //  If map The length exceeds the maximum , Take out map The first element in , Then delete 
            const delKey = data.keys().next().value
            data.delete(delKey);
        }
    }
    get(key) {
        const data = this.data;
        //  data map There is no key Corresponding data , Then return to null
        if (!data.has(key)) return null;
        const value = data.get(key);
        //  Before returning data , Delete the original data first , And then add , You can keep it up to date 
        data.delete(key);
        data.set(key, value);
        return value;
    }
}

Test it ：

const lruCache = new LRUCache(2);
lruCache.set('1', 1); // Map(1) {1 => 1}
lruCache.set('2',2); // Map(2) {1 => 1, 2 => 2}
console.log(lruCache.get('1')); // Map(2) {2 => 2, 1 => 1}
lruCache.set('3',3); // Map(2) {1 => 1, 3 => 3}
console.log(lruCache.get('2')); // null
lruCache.set('4',4); // Map(2) {3 => 3, 4 => 4}
console.log(lruCache.get('1')); // null
console.log(lruCache.get('3')); // Map(2) {4 => 4, 3 => 3}
console.log(lruCache.get('4')); // Map(2) {3 => 3, 4 => 4}

Running results ：

Use Map Basically, it can be done LRU cache , And its compatibility can also , except IE Compatibility is poor ：

If not used Map, So what else can you do LRU Cache ？

Use Object + Array Realization LRU cache

Just now we also analyzed ,LRU Two things need to be met ： Key value pairs and sortable , These two points can correspond to Object and Array, So can we take this as a way of thinking ？ The answer is yes , Take a quick look at the implementation code ：

class LRUCacheObjArr {
    length = 0; //  Define the maximum length of the list 
    dataObj = {}; //  Use objects to stage data , Where warrantable get The time complexity is O(1)
    dataArr = []; //  Use arrays to solve ordered problems 
    constructor(length) {
        if (length < 1) throw new Error(' invalid parameter ')
        this.length = length;
    }
    get(key) {
        if (!this.dataObj[key] || !this.dataArr.length) return null;
        //  The value to be accessed , Put it back at the end of the array , Represents the latest data 
        const index = this.dataArr.findIndex(item => item.key === key);
        //  Delete the original data first , then push To the end of the array 
        this.dataArr.splice(index, 1);
        this.dataArr.push(this.dataObj[key]);
        //  Return value , The object is disordered , We just need to ensure that the data in it is up-to-date 
        return this.dataObj[key].value;
    }
    set(key, value) {
        //  Define object data 
        const obj = {key, value};
        const index = this.dataArr.findIndex(item => item.key === key);
        //  Determine whether to add or modify 
        if (index !== -1) {
            //  If data already exists , Delete first , then push To the end 
            this.dataArr.splice(index, 1);
            this.dataArr.push(obj);
        } else {
            //  If there is no data , Then the array is directly push
            this.dataArr.push(obj);
        }
        //  Object adds or modifies the same object 
        this.dataObj[key] = obj;
        //  After judging the new data , Whether the maximum length is exceeded 
        if (this.dataArr.length > this.length) {
            //  Arrays are ordered , If it is too long, delete it directly from the head , And get the deleted data 
            const tmp = this.dataArr.shift();
            //  The currently deleted object should also be deleted from the data object , Avoid being picked up again 
            delete this.dataObj[tmp.key];
        }
    }
}

Let's use the same test case to test ：

const lruCache = new LRUCacheObjArr(2);
lruCache.set('1', 1); // dataArr(1) [obj1], dataObj(1) {'1': obj1}
lruCache.set('2',2); // dataArr(2) [obj1, obj2], dataObj(2) {'1': obj1, '2': obj2}
console.log(lruCache.get('1')); // dataArr(2) [obj2, obj1], dataObj(2) {'1': obj1, '2': obj2}
lruCache.set('3',3); // dataArr(2) [obj1, obj3], dataObj(2) {'1': obj1, '3': obj3}
console.log(lruCache.get('2')); // null
lruCache.set('4',4); // dataArr(2) [obj3, obj4], dataObj(2) {'3': obj3, '4': obj4}
console.log(lruCache.get('1')); // null
console.log(lruCache.get('3')); // dataArr(2) [obj4, obj3], dataObj(2) {'3': obj3, '4': obj4}
console.log(lruCache.get('4')); // dataArr(2) [obj3, obj4], dataObj(2) {'3': obj3, '4': obj4}

Running results ：

Use object + Array way , Although the effect can be achieved , But because of the frequent operation of arrays , So it's going to sacrifice some performance , And there is no Map convenient . In addition to using arrays + object , In fact, we can also use a two-way linked list LRU.

Use a two-way list DoublyLinkedList Realization LRU

Double linked list , As the name suggests, it is a linked list in two directions , This is different from the one-way linked list . It may be more intuitive to look at the picture directly ：

The one-way linked list only has next, No, pre. When a two-way linked list moves elements , It will be a little more complicated than the one-way linked list , For example, we want to put B and C Nodes swap positions , The process is as follows ：

This corresponds to LRU What is it ？ A two-way linked list is ordered , Each node knows its previous or next node ; The way to store values is also the way to use key value pairs , Therefore, it can be realized LRU.

Implementation code ：

  class LRUCacheLinked {
      data = {}; //  Linked list data 
      dataLength = 0; //  Chain length , Use variables to save , Faster access to 
      listHead = null; //  List the head 
      listTail = null; //  List the tail 
      length = 0; //  Maximum length of linked list 
      //  Constructors 
      constructor(length) {
        if (length < 1) throw new Error(' Illegal parameter ')
        this.length = length;
      }
      set(key, value) {
        const curNode = this.data[key];
        if (curNode == null) {
          //  The new data 
          const nodeNew = {key, value};
          //  Move to the end 
          this.moveToTail(nodeNew);
          //  Save the new node to the data object , Its pre or next Will be in moveToTail Set in 
          this.data[key] = nodeNew;
          //  The length of the linked list increases 
          this.dataLength++;
          //  Initialize the linked list header 
          if (this.dataLength === 1) this.listHead = nodeNew;
        } else {
          //  Modify existing data 
          curNode.value = value;
          //  Move to the end 
          this.moveToTail(curNode);
        }
        //  Adding data may cause the length to be exceeded , So try deleting the data 
        this.tryClean();
      }

      get(key) {
        //  according to key Value to get the corresponding node 
        const curNode = this.data[key];
        if (curNode == null) return null;
        if (this.listTail === curNode) {
          //  If the accessed element is at the end of the linked list , The value is returned directly , And there is no need to modify the linked list 
          return curNode.value;
        }
        //  If it is an intermediate element or a header element , You need to move it to the end of the linked list before getting it , Means the latest 
        this.moveToTail(curNode);
        return curNode.value;
      }
      //  Move the node to the end of the linked list 
      moveToTail(curNode) {
        //  Get the tail of the linked list 
        const tail = this.listTail;
        //  If the current node is the end of the linked list , Do not deal with , Go straight back to 
        if (tail === curNode) return;
        // 1. preNode and nextNode Sever and curNode The relationship between 
        const preNode = curNode.pre;
        const nextNode = curNode.next;
        if (preNode) {
          if (nextNode) {
            //  The previous node of the current element points to its next node 
            preNode.next = nextNode;
          } else {
            //  Disconnect the current element from the previous node 
            delete preNode.next;
          }
        }
        if (nextNode) {
          if (preNode) {
            //  The next node of the current element points to its previous 
            nextNode.pre = preNode;
          } else {
            //  Disconnect the current element from the next node 
            delete nextNode.pre;
          }
          //  If the current node is a linked list header , You need to re assign 
          if (this.listHead === curNode) this.listHead = nextNode;
        }

        // 2. curNode Sever and preNode and nextNode The relationship between 
        delete curNode.pre
        delete curNode.next

        // 3.  stay list At the end of , Rebuild curNode New relationship 
        if (tail) {
          tail.next = curNode;
          curNode.pre = tail;
        }
        //  Reassign the end of the linked list , Keep up to date 
        this.listTail = curNode;
      }
      tryClean() {
        while(this.dataLength > this.length) {
          const head = this.listHead;
          if (head == null) throw new Error(' The linked list lacks a header ');
          const headNext = head.next;
          if (headNext == null) throw new Error(' The next node is missing from the head of the linked list ');
          // 1.  Cut off head and headNext The relationship between 
          delete head.next;
          delete headNext.pre;
          // 2.  Reassign listHead
          this.listHead = headNext;
          // 3.  clear data
          delete this.data[head.key];
          // 4.  Recount 
          this.dataLength = this.dataLength - 1;
        }
      }
    }

Look at this , Two way linked list is the most complicated of the three methods . Let's use the same case to test ：

const lruCache = new LRUCacheLinked(2);
lruCache.set('1', 1);
lruCache.set('2',2);
console.log(lruCache.get('1'));
lruCache.set('3',3);
console.log(lruCache.get('2'));
lruCache.set('4',4);
console.log(lruCache.get('1'));
console.log(lruCache.get('3'));
console.log(lruCache.get('4'));

Achieve results ：

You can find , It is also possible to use a two-way linked list . The two-way linked list may not be easy to understand , Draw two pictures for everyone to understand ：

The detailed process of moving elements in a two-way linked list

The detailed process of deleting elements in a two-way linked list

Combine these two figures , Let's look at the code above , Will it be clearer .

summary

This article summarizes three implementations LRU Caching method ：Map、 Array + object 、 Double linked list , It uses Map Is the best way . Use the other two methods , Although the effect can be achieved , But in terms of efficiency 、 In terms of readability , still Map better . Have you learned all these three ways ？