LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)时间复杂度，最近访问节点置于链表头部，满时淘汰尾部最久未用节点。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。为了高效实现，通常结合哈希表和双向链表，C++中可以用 unordered_map 和自定义的双向链表来完成。
基本思路
使用一个双向链表维护访问顺序，最近访问的节点放在链表头部，最久未访问的在尾部。同时用哈希表快速定位节点位置：
- get(key)：若存在，返回值并将该节点移到链表头；否则返回 -1
- put(key, value)：若已存在，更新值并移到头部；若不存在且缓存已满，删除尾部节点，插入新节点到头部
关键数据结构设计
定义双向链表节点和缓存容量：
struct ListNode {
int key, value;
ListNode *prev, *next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
成员变量包括：
立即学习“C++免费学习笔记（深入）”；
- 头尾指针：方便插入删除
- 哈希表：unordered_map<int, ListNode*>
- 当前大小与最大容量
核心操作实现
封装两个辅助函数简化逻辑：
void removeNode(ListNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
<p>void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}</p>这两个函数用于调整节点位置，保证 O(1) 时间复杂度。
完整示例代码
#include <iostream>
#include <unordered_map>
using namespace std;
<p>class LRUCache {
private:
struct ListNode {
int key, value;
ListNode <em>prev, </em>next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>int capacity;
unordered_map<int, ListNode*> cache;
ListNode *head, *tail;
void removeNode(ListNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void moveToHead(ListNode* node) {
removeNode(node);
addToHead(node);
}
ListNode* popTail() {
ListNode* last = tail->prev;
removeNode(last);
return last;
}public: LRUCache(int cap) { capacity = cap; head = new ListNode(0, 0); tail = new ListNode(0, 0); head->next = tail; tail->prev = head; }
int get(int key) {
if (cache.find(key) == cache.end()) return -1;
ListNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
ListNode* node = cache[key];
node->value = value;
moveToHead(node);
} else {
ListNode* newNode = new ListNode(key, value);
cache[key] = newNode;
addToHead(newNode);
if (cache.size() > capacity) {
ListNode* removed = popTail();
cache.erase(removed->key);
delete removed;
}
}
}
~LRUCache() {
for (auto& pair : cache) {
delete pair.second;
}
delete head;
delete tail;
}};
使用示例
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
cout << lru.get(1) << endl; // 输出 1
lru.put(3, 3); // 淘汰 key=2
cout << lru.get(2) << endl; // 输出 -1
return 0;
}
基本上就这些。用哈希表加双向链表，能保证 get 和 put 都是 O(1) 时间复杂度，符合 LRU 的高效要求。注意手动管理内存或改用智能指针避免泄漏。
