Hash table: least recently used cache

background

The basis of hash table

Hash table is a more complex and efficient data structure , Include HashSet and HashMap, The time complexity of their query to delete an element is O（1）. Often used to optimize time efficiency . Hash tables are efficient , But not everything , If you need to sort elements , Then use TreeMap.

Design of hash table

1. Array ： Design hash table based on array , The remainder of the hash value of the element to the length of the array is used as the array subscript , The time efficiency of finding elements is O（1）.
2. Linked list ： When the hash values are equal , Array subscripts will cause conflicts , You need to store multiple elements in the same location of the array in a linked list .
3. Capacity expansion ： To ensure efficiency , When the ratio of the number of elements to the length of the array exceeds the threshold , We need to expand the length of the array .

subject

Please design and implement a least recently used cache , The time complexity of the following two operations is required to be O（1）.

• get(key)
• put(key, value)

Their thinking

This problem requires us to design a cached data structure ,

1. We have to record the order in which the nodes are accessed . If we use HashMap, Use get,put when , Time complexity can be achieved O（1）, Visit one node at a time , Let's take the node's key Store as key hashMap in , Node most HashMap Value storage for , At the same time, the node is added to the end of the linked list , In this way, the head node of the linked list is the least used node , The tail node is the newly used node .
2. Two way linked list replaces one-way linked list . Enables you to quickly delete and query nodes .

Something to watch out for ：

1. When the number of nodes exceeds the threshold , The least recently used nodes need to be eliminated .
2. With the help of sentry node , Easy to update cache .

The specific logic code is as follows ：

Code

class LRUCache {
    
   private int capacity = 0;
   private ListNode head;
   private ListNode tail;
   private Map<Integer, ListNode> cache;

    public LRUCache(int capacity) {
    
        this.capacity = capacity;// threshold 
        // Initialize cache hash table 
        cache = new HashMap<Integer, ListNode>();
        
        // Initializing a double linked list ,  Here the sentry node is used to quickly add the tail node .
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
    
        ListNode node = cache.get(key);
        if(node == null) {
    
            return -1;
        }
        moveToTail(node, node.value);
        return node.value;
    }
    
    public void put(int key, int value) {
    
        if(cache.containsKey(key)) {
    
            moveToTail(cache.get(key), value);
        } else {
    
            if(cache.size() == capacity) {
    
                ListNode tobeDeleteNode = head.next;
                deleteNode(tobeDeleteNode);
                cache.remove(tobeDeleteNode.key);
            }
             ListNode node = new ListNode(key, value);
             insertToTail(node);
             cache.put(key, node);
        }
    } 

    private void deleteNode(ListNode node) {
    
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    private void moveToTail(ListNode node, int value) {
    
        //detete
        deleteNode(node);
        //insertToTail
        node.value = value;
        insertToTail(node);
    }

    private void insertToTail(ListNode node) {
    
        node.pre = tail.pre;
        tail.pre.next  = node;
        node.next = tail;
        tail.pre = node;
    }

    class ListNode {
    
        ListNode pre;
        ListNode next;
        int key;
        int value;
        public ListNode(int key, int value){
    
            this.key = key;
            this.value = value;
        }
    }
}

/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */

summary

This topic examines the knowledge points of hash table , It should be noted that the least recently used cache needs to record the order of element access , So the data structure of the final cache is designed as hash table and bidirectional linked list .