Roll in Dachang series LRU cache elimination algorithm

LRU What is it? ？

LRU yes Least Recently Used Abbreviation , Least recently used , Is a commonly used memory elimination data algorithm , That is, eliminate the least recently used cache data .

LRU functional requirement

Please design and implement a meeting LRU ( Recently at least use ) Cache constrained data structures .

• Realization LRUCache class ：

1. LRUCache(int capacity) With Positive integer As capacity capacity initialization LRU cache .
2. int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
3. void put(int key, int value) If the keyword key Already exist , Change its data value value ; If it doesn't exist , Then insert the group into the cache key-value . If the insert operation causes the number of keywords to exceed capacity , Should be Eviction The longest unused keyword .
4. function get and put Must be O(1) The average time complexity of running .

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]

 explain 
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); //  The cache is  {1=1}
lRUCache.put(2, 2); //  The cache is  {1=1, 2=2}
lRUCache.get(1);    //  return  1
lRUCache.put(3, 3); //  This operation causes the keyword to  2  To void , The cache is  {1=1, 3=3}
lRUCache.get(2);    //  return  -1 ( Not found )
lRUCache.put(4, 4); //  This operation causes the keyword to  1  To void , The cache is  {4=4, 3=3}
lRUCache.get(1);    //  return  -1 ( Not found )
lRUCache.get(3);    //  return  3
lRUCache.get(4);    //  return  4

Realization

analysis ： To eliminate the least recently used memory data , So how to distinguish which memory data has not been used recently ？

May adopt Map structure （ Query operation O(1)） + Double linked list （ The header records old data , The tail records new data ）

In a two-way list , Add the data according to the tail , Those close to the head represent those who are earlier in time （ Join the team early ）, Far from the head means it's a little late （ After that, I joined the team ）, Add... According to the tail , Head deletion principle , Close to the head represents the least recently used data , That is to eliminate the data in the head of the linked list, which represents the least recently used data .

The two-way linked list operation is summarized as follows ：

1. Add nodes at the end
2. Get elements （get operation ） That is, the element , You need to move the element to the end of the linked list （ Represents the recent use of this data ）
3. Additive elements （put operation ） That is, the element , If the element exists , Update element data , At the same time, you also need to move the element to the end of the linked list （ Represents the recent use of this data ）, If the element does not exist , It is directly added to the tail of the linked list .
4. When adding elements , Capacity needs to be considered , If it exceeds the current capacity , Then remove the head element of the linked list （ Represents data that has not been operated recently ）

public class LRUCache {
    

    private MyCache<Integer, Integer> cache;

    public LRUCache(int capacity) {
    
        cache = new MyCache<>(capacity);
    }

    public int get(int key) {
    
        Integer ans = cache.get(key);
        return ans == null ? -1 : ans;
    }

    public void put(int key, int value) {
    
        cache.set(key, value);
    }

    //  The node structure 
    public static class Node<K, V> {
    
        public K key;
        public V value;
        public Node<K, V> pre;
        public Node<K, V> next;

        public Node(K key, V value) {
    
            this.key = key;
            this.value = value;
        }
    }

    //  Double linked list structure 
    public static class NodeDoubleLinkedList<K, V> {
    
        private Node<K, V> head;
        private Node<K, V> tail;

        public NodeDoubleLinkedList() {
    
            head = null;
            tail = null;
        }

        //  Add nodes at the end 
        public void addNode(Node<K, V> newNode) {
    
            if (newNode == null) {
    
                return;
            }
            if (head == null) {
    
                head = newNode;
                tail = newNode;
            } else {
    
                tail.next = newNode;
                newNode.pre = tail;
                tail = newNode;
            }
        }

        //  Move the nodes on the linked list to the tail 
        public void moveNodeToTail(Node<K, V> node) {
    
            if (tail == node) {
    
                return;
            }
            // node  Not the tail 
            if (head == node) {
    
                head = node.next;
                head.pre = null;
            } else {
    
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            node.pre = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }

        //  Remove the head node 
        public Node<K, V> removeHead() {
    
            if (head == null) {
    
                return null;
            }
            Node<K, V> res = head;
            if (head == tail) { //  When there is only one node in the linked list 
                head = null;
                tail = null;
            } else {
    
                head = res.next;
                res.next = null;
                head.pre = null;
            }
            return res;
        }

    }

    public static class MyCache<K, V> {
    

        private HashMap<K, Node<K, V>> keyNodeMap;
        private NodeDoubleLinkedList<K, V> nodeList;
        private final int capacity;

        public MyCache(int cap) {
    
            if (cap < 1) {
    
                throw new RuntimeException("should be more than 0.");
            }
            keyNodeMap = new HashMap<>();
            nodeList = new NodeDoubleLinkedList<>();
            capacity = cap;
        }

        public V get(K key) {
    
            if (keyNodeMap.containsKey(key)) {
    
                Node<K, V> res = keyNodeMap.get(key);
                nodeList.moveNodeToTail(res);
                return res.value;
            }
            return null;
        }

        public void set(K key, V value) {
    
            if (keyNodeMap.containsKey(key)) {
    
                Node<K, V> node = keyNodeMap.get(key);
                node.value = value;
                nodeList.moveNodeToTail(node);
            } else {
    
                if (keyNodeMap.size() == capacity) {
    
                    removeMostUnusedCache();
                }
                Node<K, V> newNode = new Node<>(key, value);
                keyNodeMap.put(key, newNode);
                nodeList.addNode(newNode);
            }
        }

        private void removeMostUnusedCache() {
    
            Node<K, V> removeNode = nodeList.removeHead();
            keyNodeMap.remove(removeNode.key);
        }

    }
}

- END -