小工具知识网

当前位置: 首页 > 行业知识 > 【算法】LRU缓存算法的C++实现

行业知识

【算法】LRU缓存算法的C++实现

2026-11-21 01:28:52 来源:互联网转载

一、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遗嘱消息?

下一篇:服务器新上线怎么设置网络?