Hand tearing algorithm -- LRU cache elimination strategy, asked so often

as everyone knows , The size of the cache is limited ！ When the cache is full , This requires a cache elimination strategy to determine which data should be cleaned out .
There are three common strategies ： First in, first out strategy FIFO（First In,First Out）、 Use strategy at least LFU（Least Frequently Used）、 Least recently used strategy LRU（Least Recently Used）.

look down LeetCode On this road LRU Design questions ：

1. Please design and implement a meeting   LRU ( Recently at least use )  cache   Constrained data structure .

 Realization  LRUCache  class ：

LRUCache(int capacity)  With   Positive integer   As capacity  capacity  initialization  LRU  cache 
int get(int key)  If the keyword  key  In the cache , The value of the keyword is returned , Otherwise return to  -1 .
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 .

 Be careful ： function  get  and  put  Must be  O(1)  The average time complexity of running .

You can see from the title , The average time complexity required is O(1). I suddenly thought of my sophomore year , The data structure teacher said , Once the key and value appear , Hash tables bear the brunt ！ Because it can be in O(1) Find keys and values in time .

For the requirements of inconsistent order , The first data structure to consider is stack 、 Linked list 、 queue . however LRUCache It's going on get() and put() After updating the data , You need to set the data to the latest accessed data , That means the data needs to be able to be accessed randomly 、 You need to insert this data into the head or tail .

Linked list is the location of nodes that can be moved quickly , But implementing random access , It can be considered that the time complexity of hash table is O(1).
If the value of the hash table contains the location information of the linked list , Then you can O(1) Access the linked list in time ！ Because the linked list can record the time sequence of access （ The earlier access is at the end of the linked list ）, Therefore, the elements in the linked list must store keys , So we can find the key in the hash table , And then realize the requirement of deleting the key in the hash table ！

1. First we design get() When the method is used , does Get value and can't get In both cases ！

• Take the value , Except to return the value , In order to meet the principle of least recent use , Also note that the node should be moved to the head of the linked list （ Because the closer you get to the tail, the earlier you visit ）, And delete the original node .
• Can 't get value , return -1 that will do .

 public int get(int key) {
    
        DLinkedNode node = cache.get(key);
        if (node == null) {
    
            return -1;
        }
        //  If  key  There is , First, locate through the hash table , And then to the head 
        moveToHead(node);
        return node.value;
    }

2. Design put() When the method is used , You need to consider There is no such thing in the cache key And already exist key In both cases ！

• There is no such thing in the cache key when , Create a new node , In order to meet the principle of least recent use , Put the new node in the head of the linked list . The most important point , Remember to determine whether the current cache size exceeds the maximum capacity ！ If you exceed , Let's just delete one of the tail nodes ！
• The... Already exists in the cache key when , We just need to modify it value value , And move the node to the head of the linked list , Remember to delete the original node .

public void put(int key, int value) {
    
        DLinkedNode node = cache.get(key);
        if (node == null) {
    
            //  If  key  non-existent , Create a new node 
            DLinkedNode newNode = new DLinkedNode(key, value);
            //  Add to hash table 
            cache.put(key, newNode);
            //  Add to the head of the bidirectional list 
            addToHead(newNode);
            ++size;
            if (size > capacity) {
    
                //  If the capacity is exceeded , Delete the tail node of the bidirectional linked list 
                DLinkedNode tail = removeTail();
                //  Delete the corresponding entry in the hash table 
                cache.remove(tail.key);
                --size;
            }
        }
        else {
    
            //  If  key  There is , First, locate through the hash table , Revise  value, And move to the head 
            node.value = value;
            moveToHead(node);
        }
    }

public class LRUCache {
    
    class DLinkedNode {
    
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {
    }
        public DLinkedNode(int _key, int _value) {
    key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
    
        this.size = 0;
        this.capacity = capacity;
        //  Using pseudo head and pseudo tail nodes 
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
	private void addToHead(DLinkedNode node) {
    
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
    
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
    
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
    
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
 }