Okay, some of you might think THAT I’m a bit of a tagline, but I want to tell you that a while back the interview was really tied to the design of the RLU caching algorithm. When doing the problem, I think too much, feel the design of a LRU(Least recently used) cache algorithm, not so simple ah, so understand the wrong meaning of the question (I am also take, can also understand into such ，，，，), their wave of operation to write a lot of code, then stuck, and then to look carefully at the problem, It is so simple to design an LRU cache algorithm.

According to the truth, if you are really familiar with this algorithm, you can write it in ten minutes. However, although I understand the idea of LRU cache algorithm and know the specific steps, BUT I have never written it before, resulting in writing, very unskilled, that is to say, Feeling like you know how to do it is not the same thing as being able to code it perfectly, so make sure you code what you think you know, if you can. Don’t think that if you understand the idea, you don’t have to write the code.

Today I take you to use the code to implement the LRU cache algorithm, later you encounter this type of problem, ensure that you perfect seconds kill it.

Topic describes

Design and implement least-used (LFU) data structures. It should support the following operations: GET and PUT.

Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise returns -1.

Put (key, value) – Set or insert a value if the key does not exist. When the cache reaches its capacity, it should invalidate the least frequently used items before inserting new ones. In this problem, when there is a tie (that is, two or more keys with the same frequency of use), the least recently used key is removed.

Advanced:

Can you perform two operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache(2 /* capacity (cache capacity) */); cache.put(1, 1); cache.put(2, 2); cache.get(1); // return 1 cache. Put (3, 3); // remove key 2 cache.get(2); // return -1 (key 2 not found) cache.get(3); // return 3 cache. Put (4, 4); // remove key 1 cache.get(1); // return -1 (key 1 not found) cache.get(3); // return 3 cache.get(4); / / return 4Copy the code

Basic edition: single linked list to solve

We want to delete the least recently used nodes, and an easy way to do this is to use a single linked list as a data structure. When we perform the put operation, the following situations occur:

1, If the put(key,value) already exists in the list, then we need to delete the old data from the list and insert the new data into the head of the list. ,

2, If the data to put(key,value) does not exist behind the list, we need to determine whether the cache is full. If so, delete the node at the end of the list, and insert the new data into the head of the list. If not, insert data directly into the head of the list.

For get operations, the following happens

1. If the data to get(key) exists in the list, return value, delete the node, and insert it into the head of the list.

If the key to get(key) does not exist behind the list, return -1.

The general idea is this, do not feel very simple, let you write, ten minutes you may not write out. The specific code, in order not to affect the reading, I put it at the end of the article.

Time and space complexity analysis

For this method, both PUT and GET need to traverse the list to see if the data exists, so the time complexity is O(n). The space complexity is O(1).

Space for time

In practical applications, when we want to read a data, we will first determine whether the data exists in the cache, if it does, we will return, if it does not exist, we will go to other places to find the data (such as disk), after finding the data stored in the cache, and then return.

Therefore, in practical applications, PUT operation is generally accompanied by GET operation, that is to say, the number of GET operation is relatively large, and the hit ratio is relatively high, and the number of PUT operation is relatively small. We can consider the way of space for time to speed up our GET operation.

For example, we can use an extra hash table (such as a HashMap) to store key-values, so that our get operation can find the target node in O(1) time and return the value.

However, can get really be done in O(1) time with a hash table?

With a hash table, although we can find the target in the O (1) the time element, can, we also need to delete the element, the element is inserted and to list the head ah, delete an element, we need to go to the elements of the precursor, and then locate precursors to this element, is the need to O (n) time complexity.

The end result is that, with hash tables, the worst time is O(1), and the space is O(n).

Bidirectional linked list + hash table

We have been able to find the O (1) time complexity to delete the node, the reason also take O (n) time complexity to delete, mainly is the time is spent on node precursor to find, in order to solve this problem, in fact, we can replace singly linked lists with double linked list, so, we can well solve the problem, moreover, When you switch to a double-linked list, you’ll find that it’s a lot easier to do than a single-linked list.

Therefore, our final solution is: double linked list + hash table. By using the combination of these two data structures, our GET operation can be completed in O(1) time complexity. Since the nodes to be removed by the PUT operation are usually tail nodes, we can use a variable tai to record the position of the tail node. In this case, our PUT operation can also be completed in O(1) time.

The specific code is as follows:

Class LRUNode{String key; Object value; LRUNode next; LRUNode pre; public LRUNode(String key, Object value) { this.key = key; this.value = value; }}Copy the code
// LRU public class LRUCache { Map<String, LRUNode> map = new HashMap<>(); RLUNode head; RLUNode tail; Int capacity = 1; int capacity = 1; public RLUCache(int capacity) { this.capacity = capacity; } public void put(String key, Object value) {if (head == null) {
            head = new LRUNode(key, value);
            tail = head;
            map.put(key, head);
        }
        LRUNode node = map.get(key);
        if(node ! = null) {// Update node.value = value; RemoveAndInsert (node); }else{ LRUNode tmp = new LRUNode(key, value); // If overflow occursif(map.size() >= capacity) {// remove map.remove(tail); // Delete the tail node tail = tail.pre; tail.next = null; } map.put(key, tmp); // Insert tmp.next = head; head.pre = tmp; head = tmp; } } public Object get(String key) { LRUNode node = map.get(key);if(node ! = null) {removeAndInsert(node);return node.value;
        }
        returnnull; } private void removeAndInsert(LRUNode node) {private void removeAndInsert(LRUNode node) {private void removeAndInsert(LRUNode node) {private void removeAndInsert(LRUNode node)if (node == head) {
            return;
        } else if (node == tail) {
            tail = node.pre;
            tail.next = null;
        } else{ node.pre.next = node.next; node.next.pre = node.pre; } // Insert the head node node.next = head; node.pre = null; head.pre = node; head = node; }}Copy the code

It is important to note that for linked list data structures, head and tail nodes are special points. If the nodes to be deleted are either head or tail nodes, they should be processed first.

Let me put the single linked list version here

Class RLUNode{String key; Object value; RLUNode next; public RLUNode(String key, Object value) { this.key = key; this.value = value; }} RLU public class RLUCache {RLUNode head; int size = 0; Int capacity = 0; Public RLUCache(int capacity) {this.capacity = capacity; } public Object get(String key) { RLUNode cur = head; RLUNode pre = head; // Point to the precursor of the node to be deleted // find the corresponding node and put the corresponding node at the head of the list // consider special cases firstif(head == null)
            return null;
        if(cur.key.equals(key))
            returncur.value; Cur = cur.next;while(cur ! = null) {if (cur.key.equals(key)) {
                break; } pre = cur; cur = cur.next; } // the node is not foundif (cur == null)
            returnnull; Pre.next = cur.next; // Insert a cur.next = head; head = cur;returncur.value; } public void put(String key, Object value) {// If the maximum capacity is 1, there is no way ，，，，，if(capacity == 1) { head = new RLUNode(key, value); } RLUNode cur = head; RLUNode pre = head; // Check if the list is emptyif (head == null) {
            head = new RLUNode(key, value);
            return; } // Check whether the node exists // Check whether the first node is specialif (head.key.equals(key)) {
            head.value = value;
            return;
        }
        cur = cur.next;
        while(cur ! = null) {if (cur.key.equals(key)) {
                break; } pre = cur; cur = cur.next; } // The key of the node to be inserted already exists, so update the value and place it in the first nodeif(cur ! = null) { cur.value = value; pre.next = cur.next; cur.next = head; head = cur; }elseRLUNode TMP = new RLUNode(key, value); // The node does not existif(size >= capacity) {// Remove the last node cur = head;while(cur.next ! = null && cur.next.next ! = null) { cur = cur.next; } cur.next = null; tmp.next = head; head = tmp; }}}}Copy the code

If you need time, it is highly recommended to implement a wave yourself manually.

If you find this article inspiring, make it available to more people:

1, like, so that more people can see this content (collection does not like, are playing rogue -_-)

Pay attention to me and column, let us become a long-term relationship

3. Pay attention to the public account “Helpless and painful code farmer”, mainly write articles like algorithm and computer foundation, which has more than 100 original articles, I also share a lot of videos, books resources, and development tools, welcome your attention, the first time to read my article.