[LeetCode解题] -- LRU缓存机制_lru cache的实现伪代码

146. LRU缓存机制

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used : 最近最少使用。

重写双向链表 + HashMap   [要求 put get 方法时间复杂度为O(1) ]

[ 题目描述 ]

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
 
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 
 
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
 
示例:
 
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
 
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

[ 解题思路 ]

哈希链表。

问题：怎么保证“get 和 put 方法必须都是 O(1) 的时间复杂度”？

get 查找快 -- hashmap

put 插入快，删除快，有顺序之分 -- 双向链表

问题：“为什么必须要用双向链表”？

因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)

 

因为显然 cache 必须有顺序之分，以区分最近使用的和久未使用的数据；而且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。

 

[ 代码实现 ]
 

第一步 双链表的节点类

为了简化，key 和 val 都认为是 int 类型

class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
 

第二步 用Node 类型构建一个双链表。

        实现其【 头插 删除 删尾 获得size】 addFirst(Node x); remove(Node x); removeLast(); size();方法。将要实现的这几个需要的 API（这些操作的时间复杂度均为 O(1)。

class DoubleList {  
    // 在链表头部添加节点 x，时间 O(1)
    public void addFirst(Node x);
 
    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public void remove(Node x);
    
    // 删除链表中最后一个节点，并返回该节点，时间 O(1)
    public Node removeLast();
    
    // 返回链表长度，时间 O(1)
    public int size();
}
 

到这里就能回答刚才“为什么必须要用双向链表”的问题了，因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。

第三步  双向链表和哈希表实现 get put方法

有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚：

// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;
 
int get(int key) {
    if (key 不存在) {
        return -1;
    } else {        
        将数据 (key, val) 提到开头；
        return val;
    }
}
 
void put(int key, int val) {
    Node x = new Node(key, val);
    if (key 已存在) {
        把旧的数据删除；
        将新节点 x 插入到开头；
    } else {
        if (cache 已满) {
            删除链表的最后一个数据腾位置；
            删除 map 中映射到该数据的键；
        } 
        将新节点 x 插入到开头；
        map 中新建 key 对新节点 x 的映射；
    }
}
 

第四步 伪代码逻辑实现

class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }
    
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        Node x = new Node(key, val);
        
        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}
 

这里就能回答之前的问答题“为什么要在链表中同时存储 key 和 val，而不是只存储 val”，注意这段代码：

if (cap == cache.size()) {
    // 删除链表最后一个数据
    Node last = cache.removeLast();
    map.remove(last.key);
}

当缓存容量已满，我们不仅仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 得到。如果 Node 结构中只存储 val，那么我们就无法得知 key 是什么，就无法删除 map 中的键，造成错误。

至此，你应该已经掌握 LRU 算法的思想和实现了，很容易犯错的一点是：处理链表节点的同时不要忘了更新哈希表中对节点的映射。

第五步 完整代码

1. Node类。  int k,v ; Node next,prev;
2. DoubleList类-双向链表类。   int size  ; Node head,tail;
3. LRUCache 构造函数。  int cap;  DoubleList cache;    HashMap<Integer, Node> map;
4. get put 方法。

class LRUCache {
    // Node 类
    class Node {
        public int key, val;
        public Node next, prev;
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    //  DoubleList 类
    class DoubleList {          // 对Node的操作，无 k v 操作
 
        private Node head, tail;
        private int size;   // 双向链表 的实际size大小
 
        public void addFirst(Node node) {
            if (head == null) {
                head = tail = node;
            } else {
                Node n = head;
                n.prev = node;
                node.next = n;
                head = node;
            }
            size++;
        }
 
        public void remove(Node node) {     // node tail head
            if (head == node && tail == node) {
                head = null;
                tail = null;
            } else if (tail == node) {  // 最后 前下=null ; node.pre.next
                node.prev.next = null;
                tail = node.prev;
            } else if (head == node) {  // 开头 下前=null ; node.next.pre
                node.next.prev = null;
                head = node.next;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            size--;
        }
 
        public Node removeLast() {
            Node node = tail;
            remove(tail);               // 调用了remove()
            return node;
        }
 
        public int size() {
            return size;
        }
 
    }
    // LRUCache 构造函数 
    private int cap;                     // 双向链表 容量 capacity
    private DoubleList cache;
    private HashMap<Integer, Node> map;  // map 的 k , v
 
    public LRUCache(int capacity) {
        this.cap = capacity;
        cache = new DoubleList();
        map = new HashMap<>();
    }
    // get put 方法
    public int get(int key) {
        if(!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        put(key, val);                  // 此处调用了 put()
        return val;
    }
 
    public void put(int key, int value) {
        Node x = new Node(key, value);  
 
        if (map.containsKey(key)){
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key,x);
        } else {
            if (cap == cache.size()) {
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key,x);
        }
    }
}

对put()的理解

put 方法主要有3个

1.remove 删除缓存cache或者删除缓存cache、map中的数据

2.缓存头插 cache.addFirst(x);

3.更新map map.put(key,x);

那么索性如下写法

    public void put(int key, int value) {
        Node x = new Node(key, value);  
 
        if (map.containsKey(key)){
            cache.remove(map.get(key));
        } else {
            if (cap == cache.size()) {
                Node last = cache.removeLast();
                map.remove(last.key);
            }
           
        }
           cache.addFirst(x);
           map.put(key,x);
    }

 

写在最后，好久没白嫖别人思想了，还好自己得空实现了一版代码，此处奉上链接，以示敬意。

参考

https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/