This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

1. Title Description

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism.

Implement the LRUCache class:

  • LRUCache(int capacity)The capacity is a positive integercapacityInitialize theLRUThe cache
  • int get(int key)If the keywordkeyExists in the cache, returns the value of the keyword, otherwise returns- 1
  • void put(int key, int value)If the keyword already exists, change its data value; If the keyword does not exist, the group is insertedKeyword – Value. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values

Advanced: Can you do both in O(1) time?

Example:

Input [" LRUCache ", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2]. [4, 4], [1], [3], [4] Output [NULL, NULL, NULL, 1, NULL, -1, NULL, -1, 3, 4] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the code

Second, train of thought analysis

Let’s talk about the concept of the LRU algorithm first. (The link in the title can also be seen, which is baidu Encyclopedia about LRU)

LRU is the abbreviation of Least Recently Used. It is a memory management algorithm.

The general logic of the algorithm is that it is assumed that data that has not been used for a long time is relatively less likely to be used later. Therefore, when the amount of data reaches a certain threshold, we can remove the least recently used data

The queue

First in, first out (FIFO) the first data structure that comes to mind is a queue, for example:

LRUCache = new LRUCache(2); // Add an element lRUCache. Put (1, 1); | [{key: 1, the value: 1}] / / add the second element lRUCache. Put (2, 2); | [{key: 1, the value: 1}, {value: the key: 2, 2}] / / add a third element lRUCache. The team put (3, 3); | { key: 1, value: 1 } <- [{ key: 2, value: 2 }, { key: 3, value: 3 }, ]Copy the code

The problem, however, is that the get and PUT implementations of queues do not meet O(1) time complexity

To do these two operations in O(1) time, we need to use a special data structure hash linked list

Hash chain table

What is a hash list? To put it simply, it is the form of hash table + bidirectional linked list.

We all know that a hash table consists of several key-value pairs.

 key     key     key
-----   -----   -----   
value   value   value   
Copy the code

But the key-value pairs of a hash table are unordered, so whoever comes first is the same.

So, we need a chain of relationships that connects them all, so that they’re no longer unrelated to each other.

Every key-value pair it has a precursor key-value pair and a successor key-value pair just like a two-way list.

 key  ->  key  ->  key
-----    -----    -----   
value <- value <- value  
Copy the code

AC code

/** * list Node * @param {number} key * @param {number} value */ const Node = function (key, Value) {this.key = key this.value = value this.pre = null // next = null //} /** * LRU cache * @param {number} capacity */ const LRUCache = function(capacity) {this.head = null // this.end = null // this.capacity This.map = new map () // hash table}; @param {number} key * @return {number} */ LRUCache. Prototype. Get = function(key) {const d = This.map. get(key) // If (! D) return -1 // This. RefreshNode (d) return d.value}; /* @param {number} key * @param {number} value * @return {void} */ LRUCache. Prototype. Value) {const d = this.map.get(key) // If (! D) {// Determine whether the capacity exceeds, if the capacity exceeds, If (this.map.size >= this.capacity) {const oldKey = this.removenode (this.head) // Remove nodes from the hash table This.map. delete(oldKey)} // Add a new record (oldKey) const newNode = newNode (key, value) this.addNode(newNode) this.map.set(key, oldKey) Else {d.value = value this.refreshNode(d)}}; / * * * * @ param refresh Node Node Node * @ attach return void * / LRUCache. Attach the prototype. RefreshNode = function (Node) {/ / when the Node to the end, This.removenode (node) this.addNode(node)}; if(node === this.end) return this.removenode (node) this.addNode(node)}; / * * * * @ param delete Node Node Node * @ attach return any key * / attach LRUCache. Prototype. RemoveNode = function (Node) {/ / when there is only one Node If (node === this.head && node === this.end) {this.head = null this.end = null} // Else if(node === = this This.end) {this.end = this.end. Pre this.end. Next = null} else if (node === this.head) {this.head = null This.head. Next this.head. Pre = null else {node.pre. Next = node.next Return key of the deleted node return node.key}; / * * * * @ param add Node Node Node * @ attach return void * / LRUCache. Attach the prototype. Invoke the = function (Node) {/ / when the Node is at the end, Set the prefix of the added node to be the last node, If (this.end) {this.end. Next = node node.pre = this.end node.next = null} // Replace the end node this.end = node // Set the head node to the new node if(! this.head) this.head = node }; const lRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); // The cache is {1=1, 2=2} console.log(lRUCache. Get (1)); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} console.log(lRUCache. Get (2)); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} console.log(lRUCache. Get (1)); // Return -1 (not found) console.log(lRUCache. Get (3)); // Return 3 console.log(lRUCache. Get (4)); / / return 4Copy the code

Four,

Using queues is relatively simple, but performance is a bit disappointing

All lead to hash linked list, as long as you understand the characteristics of the hash linked list data structure, then you can use the data structure to solve the problem, and the performance is relatively good.

Note the structure of the linked list when adding, deleting, and updating nodes, head and end storage, and timely deletion of outdated data in the Map.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign