《程序员面试金典（第6版）》面试题 16.25. LRU 缓存（自定义双向链表，list库函数，哈希映射）

题目描述

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
题目传送门：面试题 16.25. LRU 缓存

• 它应该支持以下操作： 获取数据 get 和 写入数据 put 。

• 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

• 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例:

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

解题思路与代码

• 这道题我觉得还是有点迷惑性的，假如说不了解什么是LRU缓存，可能会被“删除最近最少使用”这句话给蒙蔽了双眼，而给出了错误的答案。

• 你可能以为，我需要删除的是访问次数相同的，最近的那个内存，其实不是的。

• LRU的原理是，如果数据最近被访问过，那么将来被访问的几率也更高。因此，我们在缓存满的时候，会淘汰最长时间未被访问的数据。

• 所以说，做这道题的时候，被误导了一下有点难受的。不过知道了原理，其实这道题也没有那么的困难。这道题的核心是删除最长时间未被访问过的内存，也就是说，想办法解决了这个问题，这道题也就迎刃而解了。

• 我们可以考虑用双向链表 + unordered_map 去解决这个问题，我们每次添加元素，都从头开始添加。内存满了，删除元素都从队列尾部删除，是不是完美的符合了删除最长时间不访问这个元素的需求。

• 最后，我们访问一个链表内的元素，我们就把这个元素，先从链表中删除，把它从新添加到链表头部，是不是也完美符合题意？

• 那unordered_map的作用是什么呢？它的作用就是让你快速知道你的这查找的这个元素是否在链表内，它的查找复杂度是O(1)的。

• 而双向链表的添加和删除节点的操作本身的时间复杂度也是O(1)的。所以用这两种数据结构，可以完美的去均摊这个时间复杂度。

那又因为面试官考你这道题，肯定是想要考你自定义双向链表的，而不是想看你用库函数。所以我们要自己掌握，如何创建并使用一个自定义的双向链表。

其次，这就意味着库函数的双向链表不重要了吗？恰恰相反，它也十分重要，真正的工作中，肯定也是不可能让你自己创建链表的。所以，矛盾又不矛盾。

那接下来，就看我给大家展现这两种解法的代码都是如何写的吧~

方案一：自定义双向链表 + unordered_map

• 在这道题当中，我们需要实现两个函数，get 和 put。
• get函数就是查找缓存中对应key的value。put函数就是把元素放到容器内，如果容器满了，就挑一个删除了，再添加。
• 根据题意，当容器满了时，我们要删除的元素是，最长时间未被使用的元素，这里我们使用的容器是双向链表，我们每次都从链表的头部开始添加元素，如果容器满了，需要删除的元素就一定是容器尾部的元素。
• 再者，我们如果查询了这个元素，而这个元素又在容器内的话，我们就要把它重新移动到头部，那如何移动呢？自然是删除后再添加啦，从当前位置删除，从链表头部添加。
• 这个自定义双向链表，我设置两个哨兵节点，分别是head与tail，这会使等会的链表操作变得非常的简单。具体的双向链表的其他实现，就请大家来看看代码啦~

具体的代码如下：

class LRUCache {
public:struct Node{int key;int val;Node * prev;Node * next;Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr){};};LRUCache(int capacity) : cap(capacity), size(0), head(new Node(-1,-1)), tail(new Node(-1,-1)) {head->next = tail;tail->prev = head;}int get(int key) {if(map.find(key) == map.end()) return -1;moveNode(map[key]);return map[key]->val;}void put(int key, int value) {if(map.find(key) != map.end()){map[key]->val = value;moveNode(map[key]);}else{if(size == cap){map.erase(tail->prev->key);removeFromList(tail->prev);--size;}Node * node = new Node(key,value);addToHead(node);map[key] = node;++size;}}
private:int cap;int size;Node * head;Node * tail;unordered_map<int,Node*> map;void addToHead(Node * node){node->next = head->next;node->prev = head;head->next->prev = node;head->next = node;}void removeFromList(Node * node){node->next->prev = node->prev;node->prev->next = node->next;}void moveNode(Node * node){removeFromList(node);addToHead(node);}
};

复杂度分析：

这个 LRU 缓存的实现，无论是 get 还是 put 操作，都可以在常数时间内完成，因此时间复杂度是 O(1)。

• 这是因为,我们通过哈希表实现了对任意键值的快速查询，查询的时间复杂度是 O(1)。

  • 对于哈希表中存储的每个键值对，我们都有一个对应的链表节点。当需要将某个键值对提到最近使用的位置时，我们可以直接通过哈希表找到对应的链表节点，然后在 O(1) 时间内将其移动到链表的头部。同样，当缓存容量已满，需要淘汰最久未使用的键值对时，我们也可以在 O(1) 时间内从链表尾部删除一个节点。

• 对于空间复杂度，因为哈希表和链表都存储了整个数据，所以空间复杂度是 O(capacity)，其中 capacity 是缓存的最大容量。

方案二：使用list + unordered_map

• 这种做法，最大的好处就是带你重新复习了一遍list容器中，各种函数的操作。如果你对list函数的操作不太熟悉的话，你可以看下我写的这篇文章：全面理解：C++中list（双向链表）容器的基础概念与函数解析

其他没什么了，代码的逻辑和上一种一模一样。

具体的代码如下：

class LRUCache {
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {if(map.find(key) == map.end()) return -1;cache.splice(cache.begin(),cache,map[key]);return map[key]->second;}void put(int key, int value) {if(map.find(key) != map.end()){cache.splice(cache.begin(),cache,map[key]);map[key]->second = value;}else{if(cache.size() == cap){map.erase(cache.back().first);cache.pop_back(); }cache.push_front({key,value});map[key] = cache.begin();}}
private:int cap;list<pair<int,int>> cache;unordered_map<int,list<pair<int,int>>::iterator> map;
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

复杂度分析：

时间复杂度：

• get 方法：O(1)。unordered_map 用哈希实现，所以查找的平均时间复杂度是O(1)，list::splice方法的时间复杂度也是O(1)。
• put 方法：O(1)。unordered_map的插入和删除操作的平均时间复杂度都是O(1)，list::push_front和list::pop_back也都是O(1)。

空间复杂度：

• O(capacity)。list和unordered_map都存储了缓存中的所有元素，所以空间复杂度与缓存的容量成正比。

这就是为什么我们使用 list 和 unordered_map 结构来实现 LRU 缓存的原因，它们可以确保所有操作都在常数时间复杂度内完成，而且空间复杂度与缓存的容量成正比。

总结

这道题主要是为了测试你对LRU（Least Recently Used）缓存淘汰策略的理解和实现能力，同时也在考察你的数据结构设计能力。

• LRU缓存淘汰策略在实际中广泛应用，例如在数据库缓存、浏览器缓存等场景中，都会有其身影。其核心思想是“如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小”。因此，这种算法可以用于预测哪些数据应该被替换出去，从而使缓存的命中率最大。

• 实现这个策略需要用到的数据结构包括哈希表（HashMap）和双向链表（Doubly LinkedList）。其中，哈希表提供了快速查找，而双向链表则可以用来调整数据的优先级。

通过这道题，你可以锻炼并展示出你对以上各种技术和数据结构的掌握程度。同时，这也是一种非常实用的技能，可以直接应用于你未来的项目和工作中。

最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。