The LRU Cache scenario is described in the previous section, and can be solved with the help of Map structure under ES6 conditions. This article will introduce a more accurate solution under ES5 conditions.

Or a brief introduction of the scene requirements, convenient did not see the previous students can also directly see (incidentally gather some words) :

When a user visits a different site, the browser needs to cache some information about the corresponding site. The next time a user visits the same site, the browser can read the cache to achieve faster access. The space allocated by the cache is limited. Therefore, when the space is insufficient, you need to delete the data that is not frequently used to implement cache management.

Need to sort out

Further paring the above scenario issues into code requirements: Implement a class that provides the following functionality:

  1. provideputMethod used to write different cached data, assuming that each piece of data is of the form} {' domain ', 'info', e.g.{'https://segmentfault.com': 'some key information '}(If the data is repeatedly written to the same domain name, the new data overwrites the old data.)
  2. Is called when the cache reaches its maximumputDelete before writing to cacheLeast recently used data;
  3. providegetMethod, which is used to read cached data and move the read data toRecent usage data;
  4. Considering the performance issues, hopefullygetandsetThe operation complexity ofO(1)(Simply put, you can’t use traversal.)

Data selection

Similarly, consider the choice of data structure first. Since it is ES5, the only options are Array and Object. Array is usually used for data structures that need to be represented in order. So you need to reorder the data after each read to maintain that order. If you use an array to store data, you can’t avoid traversal, so you can only consider Object. How to express order with Object? You have to use a linked list structure.

The list is introduced

The basic content

In view of the fact that some readers of this article may be new to the linked list structure, I will give you a brief introduction here, so you can skip this section if you are familiar with it.

The structure of a linked list, as shown above, is a series of nodes and Pointers between them. (The color is used to distinguish which pointer belongs to which node.)

  • A``B``C``DBelongs to the conventional node,HeadandTailisVirtual head and tail nodes, which makes it easy to find the first and last Settings of the list;
  • For each node, it only remembers its position before and after (if it is a one-way list, it only remembers one direction; If it is a bidirectional list, you need to remember the front and back nodes separately, as shown abovepreandnextPointer to access;

The Head pre and Tail next nodes both point to NULL

Operation diagram

Again, take the bidirectional linked list as an example. When adding a node from the end, as shown in the figure, you only need to change the pointer to Tail and the actual end node (D in this case) (pay attention to the node marked in red) :

To delete a node, as shown in the figure (take NODE C as an example), you only need to connect the front and back nodes of the node and point its two Pointers to NULL:

The way of moving a node is also borrowed from the previous idea that “moving a node is equal to deleting it first and then re-inserting it in the first place”.

As shown in the figure, assuming that C node is read by get method, then C node needs to be moved to the front of the linked list to realize the change from left to right. It seems complicated, but actually it only needs to execute the following pseudo-code:

// Move the node to the first place
moveToHead(node) {
  if(node){
     // Connect B and D
    node.pre.next  = node.next;// B's next pointer points to D
    node.next.pre = node.pre; // the nex pointer to D points to B
    
    // Move the C node between head and A
    head.next.pre = node; // The pre pointer to A points to C
    node.next = head.next; // next pointer to C points to A
    node.pre = head;  // the pre pointer to the C node points to headHead. The next = node. The pre;// Head's next pointer points to C}}Copy the code

Change the pointer before and after the target node (C), the pointer before and after the head node, and the pointer before and after the ** target node (B and D)**.

The above steps only solve the complexity problem of reordering, but also need to deal with the O(1) complexity problem of get reading. Linked list structure is convenient for sorting, but difficult to read, so we also need to maintain a hash map, which can be achieved by OBjec in ES5, so the difficulty of the whole algorithm is basically completed. You can write code step by step.

Algorithm implementation

First, provide a linked list node class with the structure of domain and info, plus a pre pointer and a next pointer:

function DoubleLinkNode (domain, info){
    this.doamin = domain;
    this.info = info;
    this.pre = null;
    this.next = null;
}
Copy the code

Second, there is the LRU Cache constructor:

function LRUCache (size){
    this.size = size;
    this.hashMap = {};
    // Initialize the virtual head and tail nodes to find the list head and tail
    this.head = new DoubleLinkNode();
    this.tail = new DoubleLinkNode();
    this.head.next = this.tail;
    this.tail.pre = this.head;
}
Copy the code

And then the same thing is put first,

LRUCache.prototype.put = function (domain, info){
   // Check whether the node exists. If it does, update the corresponding information. If it does not, insert the node
   if(this.hashmap[domain]){
     const node = this.hashmap[domian]; Node. The info = info;/ / update
     this.moveToTop(node); // todo1 moves the node to the front
     return ;
   } 
   // Otherwise insert a new node
   const size = Object.keys(this.hashmap).length;
   if(size >= this.size)}{
       // If the capacity is exceeded, the least frequently used node, namely the last node, needs to be deleted first
       const node = this.tail.pre;
       this.removeNode(node); // todo2 removes the node
   }
   // Insert the new node as normal and add it to the front
   const newNode =  new DoubleLinkNode(domain, info);
   this.hashMap[domain] = info;
   this.moveToTop(node);
};
Copy the code

MoveToTop and deleteNode methods (deleteNode and moveToTop);

LRUCache.prototype.moveToTop = function (node){ head.next.pre = node; node.next = head.next; node.pre = head; Head. Next = node; }; LRUCache.prototype.deleteNode =funtion(node) {
    // To remove a node from a list is actually to connect the nodes before and after the node to isolate the target node
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null; 
    
    // Don't forget to remove the node's key from the hash table
    delete this.hashMap[node.domain];
   
}
Copy the code

Finally, the get method is also simpler:

LRUCache.prototype.get(domain) = function(){
    if (!this.hashmap[domain]) {
      return false;
    }
    const node = this.hashmap[domain];
    this.deleteNode(node)
    // Re-register because deleteNode was deleted
    this.hashmap[domain] = node;
    this.moveToTop(node);
    return node.info;
};
Copy the code

summary

In fact, the idea of bidirectional linked list is more universal than the map implementation in the previous article. This idea is not only suitable for JS, but also can be realized in C language and other languages. Also, interviews can be used to brag (anything that has nothing to do with the interview will not attract attention).

As for the structure of the linked list, the students who have the basic algorithm may be familiar with it, but it is strange to the students who have contacted it for the first time. Therefore, after careful consideration, I decided to write in more detail, and strive to make every article easier for readers to read, which is more consistent with the original intention of writing my blog.

Also long-winded, possible algorithm and source articles all don’t like (of course it is just this kind of article I wrote it is not easy to read, or do you think this is the slew a skill, not practical), relative surface by the more popular and practical knowledge of the article, after all people all have the fear, However, I think we can still do some understanding of these contents, learning algorithm ideas, on the one hand, it is helpful for friends looking for a job in the short term, but for long-term programming industry, it can also increase knowledge, exercise logic ability.

conclusion

I hope you can like and favorites your favorite articles, so that you can give me feedback to a certain extent, which articles are better written, which articles are not enough, or for the writing style and content of any comments, welcome private communication.

Last but not least, RingCentral has set up an office in Hangzhou, and can apply for long-term telecommuting to leave 996. If you are interested, you can send a private letter (contact information is available on the homepage), and you can help to promote for free