This is the 23rd day of my participation in the More text Challenge. For more details, see more text Challenge

1. Description of the topic

146. LRU caching mechanism

Using your data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:

LRUCache(int Capacity) Initializes the LRU cache with a positive integer. Capacity Int GET (int Key) Returns the value of the key if it exists in the cache, otherwise -1 is returned. Void put(int key, int value) Void put(int key, int value) If the keyword does not exist, the keyword – value group is inserted. When the cache reaches its maximum capacity, it should delete the longest unused data values before writing new data to make room for new data values.

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

Second, thinking analysis

The first idea

• When I first saw this question, I thought queue would be used, because queue FIFO can eliminate the data at the end, but if I think about it carefully, this question needs to be eliminatedLeast recent useData, if it’s just the most recent data then queues are easy to implement. Plus frequency of use involves moving data around frequently. Obviously the queue cannot be completed.
• Is there a way to add data sequentially, moving the data forward each time it is fetched? The answer is yes!LinkedHashMap
• LinkedHashMapUnfamiliar friends can simply interpret it asHashMap. The graph below showsHashMapMemory structure of

• I have made an animation to demonstrate the whole process of the above elements!!

• whileLinkedHashMapIt’s just a linked list to string together the elements

• And that’s whyLinkedHashMapIt’s stored sequentially. butLinkedHahsMapYou can’t sort by frequency of use, can you? He is known to sort by addition order!!

*LinkedHashMap* transformation

• The nativeLinkedHashMapIt’s not enough, but a quick look at the source code shows that it’s always executed after PUTafterNodeInsertionThis way. This is alsoHashMapLeft toLinkedHashMapDo the extension!

• removeNodeYou just take the first data. In order to get into this methodremoveEldestEntryJudgment.LinkedHashMapThe default is false. So we just need to override it. But how do you keep it at the back of the line when you get it? Take a closer look at the source codegetThere is a method for thisafterNodeAccess. What it does is it shifts the element of get after the value. It fits us perfectlyLRUStrategy characteristics of

• In conclusion! We useLinkedHashMapIt is very easy to implement the LRU policy!

Their implementation

• But we want to see how we do it ourselves, not how we modify existing tools. But there’s no denying how well the linkedin map has been transformed! Below we try to achieve this way!

• First we need to make sure that we need to use Hash in conjunction with a linked list. Hash We naturally use HashMap to store data in order to locate the data easily. Locating to the data will need to operate the list of data real-time shift value of the end of the list, each elimination is to remove the first list can be. In order to facilitate our operation of the linked list here must be a double linked list!

Chain table cell

• First we define an inner class! The basic cell for a linked list. It stores keys and values so you can find nodes based on what’s stored in the Hash!preNode.nextNodePoint to front and back nodes respectively

• Initializing the capacity and list size in the builder, and initializing the boundary nodes to facilitate node shifts and deletions.

• If data is not added, -1 is returned. If data has been added, the node corresponding to the data is moved to the end of the list.

• In put, we need to maintain the size of the list for the first time and check whether we need to eliminate the data. If not for the first time, we only need to update the value and the position of the corresponding node in the list

Four,

• Although execution time and memory consumption are a bit high! But I just don’t optimize.
• The main problem is in the list of movement above the complex point. We need to maintain the order between them in terms of addition order and frequency of use. As long as this order is maintained, there is no problem!