题目链接

示例

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
  1. 输入
  2. ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  3. [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
  4. 输出
  5. [null, null, null, 1, null, -1, null, -1, 3, 4]
  7. 解释
  8. LRUCache lRUCache = new LRUCache(2);
  9. lRUCache.put(1, 1); // 缓存是 {1=1}
  10. lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  11. lRUCache.get(1);    // 返回 1
  12. lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  13. lRUCache.get(2);    // 返回 -1 (未找到)
  14. lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  15. lRUCache.get(1);    // 返回 -1 (未找到)
  16. lRUCache.get(3);    // 返回 3
  17. lRUCache.get(4);    // 返回 4

解题思路

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

  • 构建双向链表节点ListNode，应包含key,value,prev,next这几个基本属性
  • 对于Cache对象来说，我们需要规定缓存的容量，所以在初始化时，设置容量大小，然后实例化双向链表的head,tail，并让head.next->tail tail.prev->head，这样我们的双向链表构建完成
  • 对于 get 操作，首先判断 key 是否存在：
    • 如果 key 不存在，则返回 -1；
    • 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
  • 对于 put 操作，首先判断 key 是否存在：
    • 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
    • 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。将一个节点移到双向链表的头部，可以分成

  1. 「删除该节点」
  2. 「在双向链表的头部添加节点」

两步操作，都可以在 O(1)时间内完成。

「小贴士」
在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

代码

  1. public class LRUCache {
  2.     class DLinkedNode {
  3.         int key;
  4.         int value;
  5.         DLinkedNode prev;
  6.         DLinkedNode next;
  7.         public DLinkedNode() {}
  8.         public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
  9.     }
  11.     private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
  12.     private int size;
  13.     private int capacity;
  14.     private DLinkedNode head, tail;
  16.     public LRUCache(int capacity) {
  17.         this.size = 0;
  18.         this.capacity = capacity;
  19.         // 使用伪头部和伪尾部节点
  20.         head = new DLinkedNode();
  21.         tail = new DLinkedNode();
  22.         head.next = tail;
  23.         tail.prev = head;
  24.     }
  26.     public int get(int key) {
  27.         DLinkedNode node = cache.get(key);
  28.         if (node == null) {
  29.             return -1;
  30.         }
  31.         // 如果 key 存在，先通过哈希表定位，再移到头部
  32.         moveToHead(node);
  33.         return node.value;
  34.     }
  36.     public void put(int key, int value) {
  37.         DLinkedNode node = cache.get(key);
  38.         if (node == null) {
  39.             // 如果 key 不存在，创建一个新的节点
  40.             DLinkedNode newNode = new DLinkedNode(key, value);
  41.             // 添加进哈希表
  42.             cache.put(key, newNode);
  43.             // 添加至双向链表的头部
  44.             addToHead(newNode);
  45.             ++size;
  46.             if (size > capacity) {
  47.                 // 如果超出容量，删除双向链表的尾部节点
  48.                 DLinkedNode tail = removeTail();
  49.                 // 删除哈希表中对应的项
  50.                 cache.remove(tail.key);
  51.                 --size;
  52.             }
  53.         }
  54.         else {
  55.             // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
  56.             node.value = value;
  57.             moveToHead(node);
  58.         }
  59.     }
  61.     // 插入头节点
  62.     private void addToHead(DLinkedNode node) {
  63.         node.prev = head;
  64.         node.next = head.next;
  65.         head.next.prev = node;
  66.         head.next = node;
  67.     }
  68.     // 移动到头节点
  69.     private void moveToHead(DLinkedNode node) {
  70.         removeNode(node);
  71.         addToHead(node);
  72.     }
  73.     // 删除节点
  74.     private void removeNode(DLinkedNode node) {
  75.         node.prev.next = node.next;
  76.         node.next.prev = node.prev;
  77.     }
  78.     // 删除尾节点
  79.     private DLinkedNode removeTail() {
  80.         DLinkedNode res = tail.prev;
  81.         removeNode(res);
  82.         return res;
  83.     }
  84. }

直接继承使用LinkedHashMap

  1. class LRUCache extends LinkedHashMap<Integer, Integer>{
  2.     private int capacity;
  4.     public LRUCache(int capacity) {
  5.         super(capacity, 0.75F, true);
  6.         this.capacity = capacity;
  7.     }
  9.     public int get(int key) {
  10.         return super.getOrDefault(key, -1);
  11.     }
  13.     public void put(int key, int value) {
  14.         super.put(key, value);
  15.     }
  17.     @Override
  18.     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  19.         return size() > capacity; 
  20.     }
  21. }