LRU缓存通过哈希表和双向链表实现O(1)操作：1. 用unordered_map映射key到节点，双向链表维护访问顺序；2. get时查map并移至链表头；3. put时更新或插入，超容则删尾结点。
LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，核心思想是：当缓存满时，优先淘汰最久未使用的数据。C++ 中实现 LRU 缓存通常结合哈希表和双向链表，以达到 O(1) 的查找、插入和删除效率。
1. 数据结构选择
要高效实现 LRU 缓存，需要两种数据结构配合：
- std::unordered_map：用于存储 key 到节点的映射，实现 O(1) 查找。
- 双向链表：维护访问顺序，最近使用的放头部，最久未使用的在尾部，便于快速删除和移动。
我们自定义一个双向链表节点：
struct Node {
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
2. 核心操作设计
LRU 缓存需要支持两个主要操作：
立即学习“C++免费学习笔记（深入）”；
- get(key)：获取键对应的值，若不存在返回 -1；存在则将其移到链表头部（表示最近使用）。
- put(key, value)：插入或更新键值对。若已存在，更新值并移至头部；若不存在且缓存已满，先删除尾部节点（最久未用），再插入新节点到头部。
3. 辅助函数：链表操作
为了简化逻辑，封装几个私有方法：
- removeNode(node)：将节点从链表中摘除。
- addToHead(node)：将节点插入到链表头部。
- moveToHead(node)：将已有节点移动到头部（先删除再添加）。
- removeTail()：删除尾节点，并从 map 中移除对应 key。
4. 完整代码实现
#include <iostream>
#include <unordered_map>
<p>class LRUCache {
private:
struct Node {
int key, value;
Node<em> prev;
Node</em> next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>std::unordered_map<int, Node*> cache;
Node* head;
Node* tail;
int capacity;
int size;
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void moveToHead(Node* node) {
removeNode(node);
addToHead(node);
}
Node* removeTail() {
Node* node = tail->prev;
removeNode(node);
return node;
}public: LRUCache(int cap) : capacity(cap), size(0) { head = new Node(0, 0); tail = new Node(0, 0); head->next = tail; tail->prev = head; }
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
Node* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
moveToHead(node);
} else {
Node* newNode = new Node(key, value);
cache[key] = newNode;
addToHead(newNode);
size++;
if (size > capacity) {
Node* removed = removeTail();
cache.erase(removed->key);
delete removed;
size--;
}
}
}
~LRUCache() {
Node* curr = head;
while (curr) {
Node* temp = curr;
curr = curr->next;
delete temp;
}
}};
5. 使用示例
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
std::cout << lru.get(1) << std::endl; // 输出 1
lru.put(3, 3); // 淘汰 key=2
std::cout << lru.get(2) << std::endl; // 输出 -1
return 0;
}
基本上就这些。这个实现保证了 get 和 put 操作都在 O(1) 时间内完成，符合 LRU 缓存的基本要求。关键点在于双向链表与哈希表的协同管理，以及对边界情况（如空链表、单节点）的正确处理。
