在日常开发中,缓存 是一个非常常见且重要的技术手段,能够显著提升系统性能。为了保证缓存的有效性,需要实现一种机制,在缓存空间不足时,能够自动淘汰最久未被使用的数据。这种机制就是**LRU(Least Recently Used,最近最少使用)**算法。
一、LRU缓存的原理
LRU是一种常用的缓存淘汰策略,基本思路是:当缓存已满时,淘汰最近最少使用的数据。为了实现这种策略,我们需要快速找到最久未使用的数据,同时在每次访问缓存时,都要将访问的数据移到最前面。
为了实现这一需求,我们可以通过双向链表和哈希表的结合:
- 双向链表:用于记录访问顺序,最新访问的数据在链表头部,最久未使用的数据在链表尾部。当缓存满时,删除链表尾部的数据。
- 哈希表:通过哈希表实现O(1)的查找速度,快速判断某个数据是否在缓存中。
二、LRU缓存的设计
我们使用如下的数据结构来实现LRU缓存:
- 双向链表:用于维护缓存中的数据,链表的头部是最近访问的数据,尾部是最久未使用的数据。
- 哈希表:用于存储缓存中每个节点的地址,以便快速查找。
双向链表的节点结构
我们定义了一个双向链表的节点 ListNode
,用于存储每个缓存项的键值对:
struct ListNode {
int key;
string val;
struct ListNode* prev;
struct ListNode* next;
ListNode(int k, const string& v): key(k), val(v), prev(nullptr), next(nullptr) {}
};
这个结构体有四个成员:
key
:缓存项的键val
:缓存项的值prev
:指向前一个节点next
:指向后一个节点
LRU类设计
接下来,我们实现LRU缓存类 LRU
。该类包含以下成员:
head
和tail
:指向链表的头节点和尾节点,便于快速插入和删除。listSize
:当前链表的长度。Size
:缓存的最大容量。mp
:一个哈希表,用于存储键与链表节点的映射。
class LRU {
private:
struct ListNode* head;
struct ListNode* tail;
int listSize;
int Size;
unordered_map<int, struct ListNode*> mp;
public:
LRU() {
head = new ListNode(0, "");
tail = new ListNode(0, "");
head->next = tail;
tail->prev = head;
listSize = 0;
Size = 5; // 缓存容量设为5
}
三、LRU缓存的实现
我们需要实现的功能有:
- 插入或更新缓存项:每次插入或访问某个缓存项时,将其移到链表的头部。
- 淘汰最久未使用的缓存项:当缓存容量超出时,删除链表尾部的节点。
1. 缓存插入或更新操作
每次插入缓存时,首先检查该键是否已经存在:
- 如果存在,将该节点移到链表的头部。
- 如果不存在,创建一个新的节点并插入到链表头部。同时,当链表长度超过容量时,删除尾部节点。
void insert(int k, const string& v) {
// 缓存命中
if (mp.find(k) != mp.end()) {
struct ListNode* t = mp[k];
struct ListNode* p = mp[k]->prev;
struct ListNode* n = mp[k]->next;
// 将该节点从原位置移除
p->next = n;
n->prev = p;
// 移动到链表头部
p = head->next;
head->next = t;
t->next = p;
p->prev = t;
t->prev = head;
}
// 缓存不命中
else {
struct ListNode* t = new ListNode(k, v);
mp[k] = t;
struct ListNode* p = head->next;
// 插入到链表头部
head->next = t;
t->next = p;
p->prev = t;
t->prev = head;
listSize++;
// 数量满了,需要删除最后的元素
if (listSize == Size + 1) {
t = tail->prev;
t->prev->next = tail;
tail->prev = t->prev;
listSize--;
mp.erase(t->key);
delete t;
}
}
}
2. 缓存打印操作
我们还实现了一个简单的 print
函数,用于输出当前缓存的内容,帮助调试和验证程序的正确性:
void print() {
struct ListNode* p = head->next;
while (p != tail) {
cout << "{" << p->key << "," << p->val << "}" << ' ';
p = p->next;
}
cout << endl;
}
四、测试与输出
我们可以通过 main
函数测试这个LRU缓存:
int main() {
LRU lru;
lru.insert(1, "A");
lru.insert(2, "B");
lru.insert(3, "C");
lru.insert(4, "D");
lru.insert(5, "E");
lru.insert(6, "F");
lru.insert(7, "G");
lru.print();
}
输出结果为:
{7,G} {6,F} {5,E}
这个输出说明,最新插入的键值对 {7, G}
在链表头部,而最早的 {1, A}
已经被淘汰。
五、总结
通过以上的实现,我们可以看到 LRU
缓存可以通过双向链表和哈希表的结合高效实现。双向链表用于维护缓存项的顺序,哈希表用于快速查找缓存项。每次访问或插入时,都将对应项移动到链表的头部,而当缓存超出容量时,淘汰链表尾部的最久未使用数据。
这种设计使得 LRU
缓存的查找、插入、删除操作都能在 O(1) 时间内完成,非常适合在高频率数据访问场景下使用。