LRU缓存-平芜编程栈

1.什么是LRU缓存

LRU缓存是一种常见的缓存淘汰算法，用于在缓存空间不足时，决定哪些数据应该被移除。它的核心思想是：当缓存已满时，优先淘汰最近最少使用的数据。

2.核心原理

假设缓存空间有限，只能存储固定数量的数据项。当需要添加新数据但缓存已满时：

(1)系统会检查缓存中所有数据

(2)选择最近最久没有被访问的数据

(3)将其移除，腾出空间给新数据

3.为什么需要LRU缓存

缓存空间有限，不可能存储所有数据
遵循“局部性原理”：最近被访问的数据，未来再次被访问的概率更高
通过保留热点数据，提高缓存命中率

4.思路

既然LRU缓存的核心是移除最久未访问过的数据，那么我们就得考虑应该如何确定哪个数据是最久未访问的。

可以使用双向链表加哈希表，每次有新的数据加入时，将其加入链表的第一个节点；当访问一个节点后，将其移到链表的第一个节点。

这样操作后，当超过缓存大小时，链表的最后一个节点就一定是最久未访问过的数据。

所以当加入一个数据后超过了缓存大小，我们就可以直接删除最后一个节点，这样删除的一定是最久未访问过的数据.

而哈希表的配合使用可以让我们在访问节点时仅需O（n）的时间复杂度，可以提高我们的查找效率，当新数据加入缓存时，将其也同步加入哈希表中，同样的删除数据时也从哈希表中删除对应数据。

通过这种方法，我们就实现了LRU缓存的核心原理并且也有最佳的查找效率。

5.实现方式

(1)使用一个双向链表,定义两个指针，一个指向前一个节点，一个指向后一个节点。

//结构体创建 struct Node{ Node* next;//指向后一个节点 Node* prev;//指向前一个节点 int val;//数据值 int key;//数据键 Node(){ this->val = 0; this->key = 0; this->next = nullptr; this->prev = nullptr; } Node(int val,int key){ this->val = val; this->key = key; this->next = nullptr; this->prev = nullptr; } };

(2)初始化成员变量

int capacity;//缓存大小 int size;//当前大小 unordered_map<int,Node*>mp;//哈希表 Node* head;//链表虚拟头节点 Node* tail;//链表虚拟尾节点

(3)当有新数据加入缓存中时，每次都将其插入到第一个节点中

void addHead(Node* p){ p->next = head->next; head->next = p; p->next->prev = p; p->prev = head; }

(4)当访问过一个数据时,将其移动到链表头部

①先将其从链表中取出

②将其添加到链表头部

//从链表中取出节点 void delNode(Node* p){ p->prev->next = p->next; p->next->prev = p->prev; } //加入链表头部 void moveHead(Node* p){ delNode(p);//调用函数从链表中取出 addHead(p);//添加到链表头部 }

(5)当超出缓存大小时,将尾部节点删除

!!注意!!:要将删除的节点内存释放,而且要防止内存泄露

void delTail(){ Node* node = tail->prev;//获取要删除的节点 mp.erase(node->key);//从哈希表中同步删除 delNode(node);//调用方法删除节点 delete node;//释放内存,防止内存泄露 node = nullptr;//避免野指针 }

(6)LRU缓存初始化

class LRUCache { public: LRUCache(int capacity) { head = new Node(); tail = new Node(); head->next = tail; tail->prev = head; this->capacity = capacity; this->size = 0; } }

(7)访问数据时

①判断该节点是否存在(哈希表)

②用一个变量接收节点

③将其移到链表第一个节点

④返回该节点的数据值

int get(int key) { //判断是否存在 if(mp.find(key)==mp.end()){ return -1; } //接收该节点 Node* node = mp[key]; //移动到第一个节点位置 moveHead(node); //返回数据值 return node->val; }

(8)加入新数据时

①判断节点是否已经存在

②得到节点

③判断是否超出缓存大小,如果超出就删除最后一个节点

④若节点不存在,则插入链表第一个节点位置,并加入哈希表中;若已经存在,则修改该节点的数据值,并将其移到链表第一个位置

void put(int key, int value) { //如果不存在 if(mp.find(key)==mp.end()){ //创建新节点 Node* node = new Node(value,key); size++;//更新当前缓存大小 //判断是否超出缓存大小 if(size>capacity){ delTail();//删除最后一个节点 } addHead(node);//加入第一个节点 mp[key] = node;//加入哈希表中 } //如果存在 else{ Node* node = mp[key];//得到节点 node->val = value;//更新数据值 moveHead(node);//移动到第一个节点的位置 } }

6.完整代码实现

class LRUCache { //结构体定义 struct Node{ Node* next; Node* prev; int val; int key; Node(){ this->val = 0; this->key = 0; this->next = nullptr; this->prev = nullptr; } Node(int val,int key){ this->val = val; this->key = key; this->next = nullptr; this->prev = nullptr; } }; private: int capacity; int size; unordered_map<int,Node*>mp; Node* head; Node* tail; //添加到头部 void addHead(Node* p){ p->next = head->next; head->next = p; p->next->prev = p; p->prev = head; } //移动到头部 void moveHead(Node* p){ delNode(p); addHead(p); } //删除节点 void delNode(Node* p){ p->prev->next = p->next; p->next->prev = p->prev; } //删除尾部节点 void delTail(){ Node* node = tail->prev; mp.erase(node->key); delNode(node); delete node; node = nullptr; } public: //初始化 LRUCache(int capacity) { head = new Node(); tail = new Node(); head->next = tail; tail->prev = head; this->capacity = capacity; this->size = 0; } //访问数据 int get(int key) { if(mp.find(key)==mp.end()){ return -1; } Node* node = mp[key]; moveHead(node); return node->val; } //插入数据 void put(int key, int value) { if(mp.find(key)==mp.end()){ Node* node = new Node(value,key); size++; if(size>capacity){ delTail(); } addHead(node); mp[key] = node; }else{ Node* node = mp[key]; node->val = value; moveHead(node); } } };