LRU (最近最少使用) 缓存机制:时间复杂度O（1）

逃离我推掉我的手 2022-05-16 14:43 136阅读 0赞

/**
      * Double Linked List
      * 用了一个特别的双向的ListNode，有了head和tail，这样就大大加快了速度。     
    * 主要加快的就是那个‘更新排位’的过程，找到item hashmap O(1), 做减法换位也都是O(1)
    * Overall O(1)
    
    *##### 巧妙点
    * 1. head和tail特别巧妙：除掉头和尾，和加上头和尾，就都特别快。    
    * 2. 用双向的pointer: pre和next, 当需要除掉任何一个node的时候，只要知道要除掉哪一个，     
    * 直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。     
    * 一旦知道怎么解决了，就不是很特别，并不是难写的算法:    
    * moveToHead()    
    * insertHead()    
    * remove() 
    **/
    public class LRUCache {
        class DoubleLinkedListNode {
            int key, val;
            DoubleLinkedListNode next,prev;
            public DoubleLinkedListNode(int key, int val){
                this.key = key;
                this.val = val;
                next = null;
                prev = null;
            }
        }
        public int capacity;
        public HashMap<Integer, DoubleLinkedListNode> map;
        public DoubleLinkedListNode head, tail;
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>();
            this.head = new DoubleLinkedListNode(-1, -1);
            this.tail = new DoubleLinkedListNode(-1, -1);
            head.next = tail;
            head.prev = tail;
            tail.next = head;
            tail.prev = head;
        }
        
        public int get(int key) {
            if(!map.containsKey(key)) {
                return -1;
            }
            DoubleLinkedListNode node = map.get(key);
            moveToHead(node);
            return node.val;
        }
        
        public void put(int key, int value) {
            if (map.containsKey(key)) {
                map.get(key).val = value;
                moveToHead(map.get(key));
            } else {
                DoubleLinkedListNode node = new DoubleLinkedListNode(key, value);
                if (map.size() >= this.capacity) {
                    DoubleLinkedListNode rm = tail.prev;
                    remove(rm);
                    map.remove(rm.key);
                }
                insertHead(node);
                map.put(key, node);
            }
        }
    
        public void moveToHead(DoubleLinkedListNode node) {
            remove(node);
            insertHead(node);
        }
        
        //Helper functions
        /*
            Put node to front, where the latest item is at.
         */
        public void insertHead(DoubleLinkedListNode node) {
            DoubleLinkedListNode next = head.next;
            head.next = node;
            node.prev = head;
            node.next = next;
            next.prev = node;
        }
    
        /*
            Find front and end, link them.
         */
        public void remove(DoubleLinkedListNode node) {
            DoubleLinkedListNode front = node.prev;
            DoubleLinkedListNode end = node.next;
            front.next = end;
            end.prev = front;
        }  
    }