行业知识
【算法】LRU缓存算法的C++实现
一、LRU简介
LRU(Least Resently Used,最近最久未使用)算法是一种缓存淘汰策略。
对于计算机来说,缓存容量是有限的,当缓存满了时就要用到LRU,对于很久没有用过的数据,我们可以将其判定为无用的数据,当新资源进入缓存或者用到了某个数据的时候,对应的资源可以判定为有用的数据,当缓存满了时我们应当优先淘汰无用的数据,而对于最近使用过的数据应当靠后淘汰,这就是LRU算法。
LRU算法也是面试时经常考察的算法题,见LeetCode146. LRU缓存,题目要求如下:
二、思路解析
在LRU缓存算法中,采用了一种有趣的数据结构——哈希链表,即HashMap+双向链表。这样一来,原本无序的哈希表就拥有了固定的排列顺序。
让我们以用户信息的需求为例,来演示一下LRU算法的基本思路:
1. 假设使用哈希链表来缓存用户信息,目前缓存了4个用户,这4个用户是按照被访问的时间顺序依次从链表右端插入的。
2. 如果这时业务方访问用户5,由于哈希链表中没有用户5的数据,需要从数据库中读取出来,插入到缓存中。此时,链表最右端是最新被访问的用户5,最左端是最近最少被访问的用户1。
3. 接下来,如果业务方访问用户2,哈希链表中已经存在用户2的数据,这时我们把用户2从它的前驱节点和后继节点之间移除,重新插入链表的最右端。此时,链表的最右端变成了最新被访问的用户2,最左端仍然是最近最少被访问的用户1。
4. 接下来,如果业务方请求修改用户4的信息。同样的道理,我们会把用户4从原来的位置移动到链表的最右侧,并把用户信息的值更新。这时,链表的最右端是最新被访问的用户4,最左端仍然是最近最少被访问的用户1。
5. 后来业务方又要访问用户6,用户6在缓存里没有,需要插入哈希链表中。假设这时缓存容量已经达到上限,必须先删除最近最少被访问的数据,那么位于哈希链表最左端的用户1就会被删除,然后再把用户6插入最右端的位置。
这就是LRU算法的基本思路。
三、具体代码
LeetCode的官方C++题解除了get()函数和put()函数外,还使用了四个函数。笔者重新整理了一下代码,只用再使用refresh()和remove()函数。
下面的代码以头部节点为最近使用的,尾部节点为最久未使用的。
首先自己定义一个双向链表,每个节点有key、value、prev指针、next指针4个属性。
class DListNode {public: DListNode(): key(0), value(0), prev(nullptr), next(nullptr) {}; DListNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}; int key, value; DListNode* prev; DListNode* next;}; LRU缓存类有5个属性:存放key值和节点地址的哈希表cache、头节点head(假头)、尾节点tail(假尾)、当前大小、容量。
class LRUCache {private: unordered_map cache; DListNode* head; DListNode* tail; int size; int capacity;} LRUcache的初始化操作如下,为了在添加节点和删除节点的时候不需要检查相邻的节点是否存在,这里使用了伪头(dummyHead)和伪尾(dummyTail),之后互相链接构成双向链表。
public: LRUCache(int _capacity): capacity(_capacity), size(0) { head = new DListNode(); tail = new DListNode(); head->next = tail; tail->prev = head; } get()函数的逻辑:如果key在哈希表中不存在则返回-1;否则先定位并refresh该节点,再返回节点的value。
int get(int key) { if (!cache.count(key)) { return -1; } DListNode* node = cache[key]; refresh(node); return node->value; } put()函数的逻辑:如果key在哈希表中不存在,则先创建一个新节点,并添加进哈希表,然后refresh该节点并更新LRUcache的大小,如果LRUcache的大小超过容量,则remove双向链表的尾部节点,删除哈希表中的对应项,并释放相应内存;
而如果key在哈希表中存在,则先通过哈希表定位,修改value,然后refresh该节点。
void put(int key, int value) { if (!cache.count(key)) { DListNode* node = new DListNode(key, value); cache[key] = node; refresh(node); size++; if (size > capacity) { DListNode* removedNode = tail->prev; remove(removedNode); cache.erase(removedNode->key); delete removedNode; size--; } } else{ DListNode* node = cache[key]; node->value = value; refresh(node); } } refresh()函数的逻辑:如果该节点在链表中,先remove该节点(判断是否处于链表中的逻辑在remove函数里),再把该节点移到头部。
void refresh(DListNode* node) { remove(node); node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } remove()函数的逻辑:先判断该节点是否处于链表中,如果是则删除该节点。
void remove(DListNode* node) { if (node->next != nullptr) { node->prev->next = node->next; node->next->prev = node->prev; } } 综上,LeetCode146. LRU缓存 的题解如下:
//新的放头部,旧的放尾部//定义一个双向链表,每个节点有key、value、prev指针、next指针4个属性class DListNode {public: DListNode(): key(0), value(0), prev(nullptr), next(nullptr) {}; DListNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}; int key, value; DListNode* prev; DListNode* next;};class LRUCache {//LRU缓存类有5个属性:存放key值和节点地址的哈希表cache、头节点head(假头)、尾节点tail(假尾)、当前大小、容量private: unordered_map cache; DListNode* head; DListNode* tail; int size; int capacity;public: //初始化 LRUCache(int _capacity): capacity(_capacity), size(0) { head = new DListNode(); tail = new DListNode(); head->next = tail; tail->prev = head; } //get函数的逻辑:如果key在哈希表中不存在则返回-1;否则先定位并refresh该节点,再返回节点的value int get(int key) { if (!cache.count(key)) { return -1; } DListNode* node = cache[key]; refresh(node); return node->value; } //put函数的逻辑:如果key在哈希表中不存在,则先创建一个新节点,并添加进哈希表,然后refresh该节点并更新LRUcache的大小, //如果LRUcache的大小超过容量,则remove双向链表的尾部节点,删除哈希表中的对应项,并释放相应内存 //如果key在哈希表中存在,则先通过哈希表定位,修改value,然后refresh该节点 void put(int key, int value) { if (!cache.count(key)) { DListNode* node = new DListNode(key, value); cache[key] = node; refresh(node); size++; if (size > capacity) { DListNode* removedNode = tail->prev; remove(removedNode); cache.erase(removedNode->key); delete removedNode; size--; } } else{ DListNode* node = cache[key]; node->value = value; refresh(node); } } //refresh函数的逻辑:如果该节点在链表中,先remove该节点(判断是否处于链表中的逻辑在remove函数里),再把该节点移到头部 void refresh(DListNode* node) { remove(node); node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } //remove函数的逻辑:先判断该节点是否处于链表中,如果是则删除该节点 void remove(DListNode* node) { if (node->next != nullptr) { node->prev->next = node->next; node->next->prev = node->prev; } }}; 四、ACM代码
代码:
//LRU缓存,以头部节点为最近使用的,尾部节点为最久未使用的#include #include using namespace std;class DListNode {public:int key, value;DListNode* prev;DListNode* next;public:DListNode() : key(0), value(0), prev(nullptr), next(nullptr) {};DListNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {};};class LRUcache {private:unordered_map cache;DListNode* head;DListNode* tail;int capacity;int size;public:LRUcache(int _capacity) {head = new DListNode();tail = new DListNode();capacity = _capacity;size = 0;head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) return -1;DListNode* node = cache[key];refresh(node);return node->value;}void put(int key, int value) {if (cache.count(key)) {DListNode* node = cache[key];node->value = value;refresh(node);}else {DListNode* node = new DListNode(key, value);cache[key] = node;refresh(node);size++;if (size > capacity) {DListNode* removedNode = tail->prev;remove(removedNode);cache.erase(removedNode->key);delete removedNode;size--;}}}void refresh(DListNode* node) {remove(node);node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void remove(DListNode* node) {if (node->next != nullptr) {node->prev->next = node->next;node->next->prev = node->prev;}}};void test() {LRUcache lru(2);lru.put(1, 1);lru.put(2, 2);cout
上一篇:服务器怎么设置mqtt遗嘱消息?
下一篇:服务器新上线怎么设置网络?