[数据结构与算法]146. LRU 缓存机制

题目

设计一个LRU（最近最久未使用）的数据结构，主要有两个操作：put（将新的键值对加入LRU）、get（取出key对应的value）

能否在 O(1) 时间复杂度内完成这两种操作？

错误思路

我刚开始知道实现一个LRU是使用一个哈希表和一个链表。

我是这样写的：
哈希表保存LRU现有的键值对；链表的头是最近最久未使用，尾是最近使用过的，这样排序的起来的。
put操作：如果LRU未满，直接加入链表的尾部，键值对加入哈希表；如果LRU满了，就要淘汰链表第一个节点，然后将新的节点加入链表尾部，键值对加入哈希表。O(1)没问题
get操作：直接在哈希表里查询是否有key，如果有，先在链表中找到这个key对应的节点，将其移动到链表的尾部，返回value；如果没有，返回-1。（在链表中查找的时间复杂度O(n)，不符合O(1)）

正确解法

上面的错误之处就在于get操作时间复杂度太高

那怎么让查找的时间复杂度为O(1)呢？也就是说，怎么让链表实现随机访问呢？
我刚开始也没想到，后来才了解到原来我们在哈希表中就保存了节点的引用，哈希表取出value时就得到了节点的位置，直接移动节点到链表最后即可。所以我们的哈希表这样声明：

Map<Integer, List_q> map;//List_q是我自己定义的链表，里面保存了key和value

能以O(1)的时间复杂度去找到对应节点，还需要把节点移动到链表尾部。

都到这里了，就不要忘掉这样一个问题：如果想把节点移动到尾部，就要找到它的前驱节点，如果用单链表那还是要O(n)复杂度，所以链表要用双向链表。

到这里已经讲完怎样实现一个LRU了，下面来看看代码：

代码实现

class LRUCache {
    class List_q{//双向链表
        int key;
        int value;
        List_q pre;
        List_q next;
        List_q(){}
        List_q(int key, int value){ 
            this.key = key;
            this.value = value;
        }
    }
    int capacity;//LRU容量
    int size;//LRU当前节点数
    List_q head, tail;//双向链表 头尾指针
    Map<Integer, List_q> map;//哈希表

    public LRUCache(int capacity) {//构造函数
        size = 0;
        this.capacity = capacity;
        head = new List_q();
        tail = head;
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            List_q p = map.get(key);//list中对应的key
            if(tail != p){//把它放到最后一个位置，代表最近使用过
                p.pre.next = p.next;
                p.next.pre = p.pre;
                tail.next = p;
                p.pre = tail;
                p.next = null;
                tail = p;
            }//如果已经是最新的，那就不用更新
            return map.get(key).value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){//如果链表中有key，那就去更新它的value
            List_q p = map.get(key);
            p.value = value;
            if(tail.key != key){//节点最近访问过，移动到链表尾部
                p.pre.next = p.next;
                p.next.pre = p.pre;
                tail.next = p;
                p.pre = tail;
                p.next = null;
                tail = p;
            }
            return ;
        }
        if(size < capacity){//LRU中没有这个key，并且LRU还未满
            List_q p = new List_q(key,value);
            map.put(key, p);
            tail.next = p;
            p.pre = tail;
            tail = p;
            size++;
        }else{//LRU满了，选择淘汰链表第一个节点
            int k = head.next.key;
            head.next = head.next.next;//剔除最近最久未使用的元素
            if(head.next != null)
                head.next.pre = head;
            List_q p = new List_q(key,value);
            tail.next = p;//最新元素放到最后
            p.pre = tail;
            tail = p;

            map.remove(k);
            map.put(key,p);
        }
    }   
}