题目

运用你所掌握的数据结构，设计和实现一个 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 

题解

这道题在今日头条、快手或者硅谷的公司中是比较常见的，代码要写的还蛮多的，难度也是 hard 级别。

最重要的是 LRU 这个策略怎么去实现, 很容易想到用一个链表去实现最近使用的放在链表的最前面。 比如 get 一个元素,相当于被使用过了，这个时候它需要放到最前面，再返回值, set 同理。 那如何把一个链表的中间元素，快速的放到链表的开头呢？ 很自然的我们想到了双端链表。

基于 HashMap 和 双向链表实现 LRU 的

整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key 的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。

LRU 存储是基于双向链表实现的，下面的图演示了它的原理。其中 head 代表双向链表的表头，tail 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

下面展示了，预设大小是 3 的，LRU 存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展示 HashMap 部分的变化，仅仅演示了上图 LRU 双向链表的变化。我们对这个 LRU 缓存的操作序列如下：

save("key1", 7) save("key2", 0) save("key3", 1) save("key4", 2) get("key2") save("key5", 3) get("key2") save("key6", 4) 

相应的 LRU 双向链表部分变化如下：

总结一下核心操作的步骤:

save(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果 LRU 空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。

get(key)，通过 HashMap 找到 LRU 链表节点，因为根据 LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。

 private static class DLinkedNode { int key; int value; DLinkedNode pre; DLinkedNode post; } /** * 总是在头节点中插入新节点. */ private void addNode(DLinkedNode node) { node.pre = head; node.post = head.post; head.post.pre = node; head.post = node; } /** * 摘除一个节点. */ private void removeNode(DLinkedNode node) { DLinkedNode pre = node.pre; DLinkedNode post = node.post; pre.post = post; post.pre = pre; } /** * 摘除一个节点,并且将它移动到开头 */ private void moveToHead(DLinkedNode node) { this.removeNode(node); this.addNode(node); } /** * 弹出最尾巴节点 */ private DLinkedNode popTail() { DLinkedNode res = tail.pre; this.removeNode(res); return res; } private HashMap<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>(); private int count; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.count = 0; this.capacity = capacity; head = new DLinkedNode(); head.pre = null; tail = new DLinkedNode(); tail.post = null; head.post = tail; tail.pre = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; // cache 里面没有 } // cache 命中,挪到开头 this.moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { DLinkedNode newNode = new DLinkedNode(); newNode.key = key; newNode.value = value; this.cache.put(key, newNode); this.addNode(newNode); ++count; if (count > capacity) { // 最后一个节点弹出 DLinkedNode tail = this.popTail(); this.cache.remove(tail.key); count--; } } else { // cache 命中,更新 cache. node.value = value; this.moveToHead(node); } } 

热门阅读

• 技术文章汇总
• [ Leetcode ] 101. 对称二叉树
• [ Leetcode ] 100. 相同的树
• [ Leetcode ] 98. 验证二叉搜索树