设计LRU缓存

LRU（Least Recently Used，最近最少使用）缓存是一种常见的缓存淘汰算法，其基本思想是：当缓存空间已满时，移除最近最少使用的数据。LRU缓存通常通过链表（双向链表）和哈希表相结合来实现，利用哈希表快速查找，链表保持数据的使用顺序。

链接：leetcode 设计LRU缓存

LRU缓存的实现思路

实现思路：哈希表 + 双向链表

• 为什么使用哈希表？
  哈希表：用来存储键值对，可以在常数时间内（O(1)）进行查找、插入和删除操作。

• 为什么使用双向带头尾链表？
  双向链表：用来维护数据的使用顺序。最近使用的元素放在链表的头部，最久未使用的元素放在链表的尾部。通过这种方式可以在O(1)的时间复杂度下实现删除最久未使用的元素。

LRU缓存的操作

• Get(key): 如果键存在于缓存中，返回对应的值并将该键值对移到链表头部，表示最近被访问过。如果不存在，返回-1。
• Put(key, value): 插入键值对。如果缓存已满，则删除最久未使用的元素，之后插入新的键值对，并将其移到链表头部。

C++11 STL实现LRU缓存

时间复杂度分析：
get(key)：查找操作是O(1)，然后通过 touch 函数将键移到链表头部，也是在O(1)时间内完成的。
put(key, value)：插入或更新键值对的操作是O(1)，如果缓存满了需要删除最久未使用的元素（evict），删除操作也是O(1)。因此，get 和 put 操作的时间复杂度都是 O(1)。

#include <iostream>
#include <unordered_map>
#include <list>class LRUCache {
public:LRUCache(int capacity) : capacity(capacity) {}// 获取缓存中的值int get(int key) {auto it = cache.find(key);if (it == cache.end()) {return -1;  // 未找到键，返回 -1}touch(it);  // 标记为最近使用return it->second.first;  // 返回对应的值}// 插入新的键值对void put(int key, int value) {auto it = cache.find(key);if (it != cache.end()) {touch(it);  // 标记为最近使用it->second.first = value;  // 更新值} else {if (cache.size() == capacity) {evict();  // 删除最久未使用的元素}// 插入新的键值对到链表头部order.push_front(key);cache[key] = {value, order.begin()};  // 存入哈希表，值和链表位置}}private:// 更新元素为最近使用void touch(std::unordered_map<int, std::pair<int, std::list<int>::iterator>>::iterator it) {int key = it->first;order.erase(it->second.second);  // 删除当前元素order.push_front(key);  // 将元素插入链表头部it->second.second = order.begin();  // 更新迭代器位置}// 淘汰最久未使用的元素void evict() {int key_to_evict = order.back();  // 获取尾部元素（最久未使用）order.pop_back();  // 从链表中移除cache.erase(key_to_evict);  // 从哈希表中删除}int capacity;  // 缓存容量std::list<int> order;  // 双向链表，维护键的访问顺序std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;  // 哈希表，存储键值对和链表位置
};int main() {LRUCache cache(2);  // 设置缓存容量为2cache.put(1, 1);    // 缓存: {1=1}cache.put(2, 2);    // 缓存: {1=1, 2=2}std::cout << cache.get(1) << std::endl;  // 返回 1，缓存: {2=2, 1=1}cache.put(3, 3);    // 淘汰键 2，缓存: {1=1, 3=3}std::cout << cache.get(2) << std::endl;  // 返回 -1 (未找到)cache.put(4, 4);    // 淘汰键 1，缓存: {3=3, 4=4}std::cout << cache.get(1) << std::endl;  // 返回 -1 (未找到)std::cout << cache.get(3) << std::endl;  // 返回 3std::cout << cache.get(4) << std::endl;  // 返回 4return 0;
}

效果：代码简洁，但效率不高。

自行设计双向链表 + 哈希表

#include <iostream>
#include <unordered_map>using namespace std;struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity) : capacity(_capacity), size(0) {// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) {return -1;  // 如果找不到该键，返回 -1}DLinkedNode* node = cache[key];moveToHead(node);  // 移动到链表头部return node->value;  // 返回值}void put(int key, int value) {if (!cache.count(key)) {// 如果 key 不存在，创建新节点DLinkedNode* node = new DLinkedNode(key, value);cache[key] = node;addToHead(node);  // 添加到链表头部++size;if (size > capacity) {// 超过容量，删除尾部节点DLinkedNode* removed = removeTail();cache.erase(removed->key);  // 从哈希表中删除该键delete removed;  // 防止内存泄漏--size;}}else {// 如果 key 存在，更新值，并移到头部DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}void moveToHead(DLinkedNode* node) {removeNode(node);  // 移除节点addToHead(node);   // 重新添加到头部}DLinkedNode* removeTail() {DLinkedNode* node = tail->prev;removeNode(node);return node;}
};int main() {LRUCache cache(2);  // 缓存容量为2cache.put(1, 1);    // 缓存: {1=1}cache.put(2, 2);    // 缓存: {1=1, 2=2}cout << cache.get(1) << endl;  // 返回 1，缓存: {2=2, 1=1}cache.put(3, 3);    // 淘汰键 2，缓存: {1=1, 3=3}cout << cache.get(2) << endl;  // 返回 -1，键 2 不存在cache.put(4, 4);    // 淘汰键 1，缓存: {3=3, 4=4}cout << cache.get(1) << endl;  // 返回 -1，键 1 不存在cout << cache.get(3) << endl;  // 返回 3cout << cache.get(4) << endl;  // 返回 4return 0;
}

代码转自力扣官方题解。
效果：时间复杂度明显降低， 效率提高。

总结

上述实现利用了哈希表和双向链表的组合，保证了LRU缓存操作的高效性。哈希表提供了O(1)的查找和更新时间，而双向链表提供了O(1)的插入和删除操作，确保了缓存的高效管理。这个实现适用于高性能缓存系统，如数据库缓存、Web缓存等。