LeetCode146——LRU缓存机制

https://blog.****.net/qq_41231926/article/details/86173740

原题链接：https://leetcode-cn.com/problems/lru-cache/description/

题目描述：

知识点：哈希表、双向链表、LRU缓存机制

思路一：用哈希表记录键值对，用双向链表处理LRU缓存机制

用示例来说明我们算法的流程，为了防止对null节点的讨论，初始化双向链表时设置虚拟头节点和虚拟尾节点，初始化的双向链表如下图所示：

（1）put(1, 1)

由于此时我们的链表容量为0，可以新增节点，且无需删除节点，这步操作后我们的链表如下图所示：

（2）put(2, 2)

由于此时我们的链表容量为1，可以新增节点，且无需删除节点，这步操作后我们的链表如下图所示：

（3）get(1)

此时我们将(1, 1)节点从链表尾部删除，并将其新增至链表头部，这步操作后我们的链表如下图所示：

（4）put(3, 3)

由于此时我们的链表容量为2，如果新增节点，就需要先删除节点，因此我们先删除(2, 2)节点，再新增(3, 3)节点。这步操作后我们的链表如下图所示：

（5）get(2)

如上图所示，链表中并没有2这个键，返回-1，无需对链表做任何操作。

（6）put(4, 4)

由于此时我们的链表容量为2，如果新增节点，就需要先删除节点，因此我们先删除(1, 1)节点，再新增(4, 4)节点。这步操作后我们的链表如下图所示：

（7）get(1)

如上图所示，链表中并没有2这个键，返回-1，无需对链表做任何操作。

（8）get(3)

此时我们将(3, 3)节点从链表尾部删除，并将其新增至链表头部，这步操作后我们的链表如下图所示：

（9）get(4)

此时我们将(4, 4)节点从链表尾部删除，并将其新增至链表头部，这步操作后我们的链表如下图所示：

整个操作过程中，由于使用了哈希表来定位节点的位置，put和get操作的时间复杂度均是O(1)。空间复杂度是O(n)，其中n为缓存容量。

感谢Back To Back SWE发布在YouTobe上的视频（需翻墙）——Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)，讲解得十分透彻清晰。

JAVA代码：

class LRUCache {
    private class Node{
        private int key;
        private int value;
        private Node pre;
        private Node next;
        public Node(){}
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    private Node dummyHead = new Node();
    private Node dummyTail = new Node();
    private int capacity;
    private int size;
    private HashMap<Integer, Node> hashMap = new HashMap<>();
    //将节点添加到虚拟头节点之后
    private void add(Node node){
        Node originHead = dummyHead.next;
        dummyHead.next = node;
        node.pre = dummyHead;
        node.next = originHead;
        originHead.pre = node;
    }
    //删除某个节点
    private void del(Node node){
        Node preNode = node.pre;
        Node nextNode = node.next;
        preNode.next = nextNode;
        nextNode.pre = preNode;
        node.pre = null;
        node.next = null;
    }
    public LRUCache(int capacity) {
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
        this.capacity = capacity;
        size = 0;
    }
    public int get(int key) {
        Node node = hashMap.get(key);
        if(null == node){
            return -1;
        }
        del(node);
        add(node);
        return node.value;
    }
    public void put(int key, int value) {
        Node node = hashMap.get(key);
        if(null != node){
            node.value = value;
            del(node);
            add(node);
        }else{
            if(size < capacity){
                size++;
            }else{
                Node delNode = dummyTail.pre;
                hashMap.remove(delNode.key);
                del(delNode);
            }
            Node newNode = new Node(key, value);
            add(newNode);
            hashMap.put(key, newNode);
        }
    }
}

LeetCode解题报告：

思路二：用LinkedHashMap实现

注意点，由于LinkedHashMap默认的LRU算法是根据键的进入顺序来定的，对于更新值和获取值的操作是忽视的，因此在更新值和获取值时我们需要先把原值删除再添进一个新值，这样实现的LRU算法才是题目所述的LRU算法。

LinkedHashMap内部的结构其实就是HashMap的基础上多个双向指针，下面给出LinkedHashMap源码中Entry的定义：

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
static class Entry<K,V> extends HashMap.Node<K,V> {
     Entry<K,V> before, after;
     Entry(int hash, K key, V value, Node<K,V> next) {
          super(hash, key, value, next);
     }
}

put和get操作的时间复杂度均是O(1)。空间复杂度是O(n)，其中n为缓存容量。

JAVA代码：

class LRUCache {
 
    private int capacity;
    private LRULinkedHashMap<Integer, Integer> lruLinkedHashMap = new LRULinkedHashMap<>();
 
    private class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            if (size() > capacity) {
                return true;
            } else {
                return false;
            }
        }
    }
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
 
    public int get(int key) {
        Integer value = lruLinkedHashMap.get(key);
        if (null == value) {
            return -1;
        }
        lruLinkedHashMap.remove(key);
        lruLinkedHashMap.put(key, value);
        return value;
    }
 
    public void put(int key, int value) {
        if (lruLinkedHashMap.containsKey(key)) {
            lruLinkedHashMap.remove(key);
        }
        lruLinkedHashMap.put(key, value);
    }
 
}