首页 > 其他分享 >使用双向链表和哈希表实现LRU缓存

使用双向链表和哈希表实现LRU缓存

时间:2024-09-27 17:50:43浏览次数:10  
标签:缓存 ListNode next 链表 LRU 哈希 prev

在日常开发中,缓存 是一个非常常见且重要的技术手段,能够显著提升系统性能。为了保证缓存的有效性,需要实现一种机制,在缓存空间不足时,能够自动淘汰最久未被使用的数据。这种机制就是**LRU(Least Recently Used,最近最少使用)**算法。

一、LRU缓存的原理

LRU是一种常用的缓存淘汰策略,基本思路是:当缓存已满时,淘汰最近最少使用的数据。为了实现这种策略,我们需要快速找到最久未使用的数据,同时在每次访问缓存时,都要将访问的数据移到最前面。

为了实现这一需求,我们可以通过双向链表哈希表的结合:

  • 双向链表:用于记录访问顺序,最新访问的数据在链表头部,最久未使用的数据在链表尾部。当缓存满时,删除链表尾部的数据。
  • 哈希表:通过哈希表实现O(1)的查找速度,快速判断某个数据是否在缓存中。

二、LRU缓存的设计

我们使用如下的数据结构来实现LRU缓存:

  1. 双向链表:用于维护缓存中的数据,链表的头部是最近访问的数据,尾部是最久未使用的数据。
  2. 哈希表:用于存储缓存中每个节点的地址,以便快速查找。
双向链表的节点结构

我们定义了一个双向链表的节点 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。该类包含以下成员:

  • headtail:指向链表的头节点和尾节点,便于快速插入和删除。
  • 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. 插入或更新缓存项:每次插入或访问某个缓存项时,将其移到链表的头部。
  2. 淘汰最久未使用的缓存项:当缓存容量超出时,删除链表尾部的节点。
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) 时间内完成,非常适合在高频率数据访问场景下使用。

标签:缓存,ListNode,next,链表,LRU,哈希,prev
From: https://blog.csdn.net/weixin_43903639/article/details/142599515

相关文章

  • 环形链表的约瑟夫问题
    一:题目二:思路前提:该题已经声明了结构体,只是看不见,声明如下:因为是从0开始实现:1:创建一个n个节点的循环链表,其值为1~n(假设n=5)如图:代码如下: structListNode*newnode=(structListNode*)malloc(sizeof(structListNode)); if(newnode==NULL) { perror("mal......
  • 数据结构编程实践20讲(Python版)—02链表
    本文目录02链表linked-listS1说明S2示例单向链表双向链表循环链表S3问题:反转单向链表求解思路Python3程序S4问题:双向链表实现历史浏览网页求解思路Python3程序S5问题:基于循环链表的玩家出牌顺序求解思路Python3程序往期链接01数组02链表linked-lis......
  • 数据结构——链表
    c++数据结构p3链表链表的每一个节点都是独立分配出来的从当前节点能够找到下一个节点Node(链表)=date(数据域)+next(地址域)地址域:存储的是下一个节点的地址最后一个地址域是nullptrstructNode{intdata;Node*next;}特点:每一个节点都是在堆内存上独立new出来......
  • 【LeetCode Hot 100】21. 合并两个有序链表
    题目描述最简单粗暴的想法是将两个链表的所有元素拿出来放在一个数组中,再将此数组排序,最后生成一个新链表并返回。由于给出的参数本身就是两个排好序的链表,可以进行一次遍历,就能保证元素仍然是有序的:每次比较当前指针指向的两个元素的大小,较小的拿出来作为当前元素并将指针向前移......
  • [Python手撕]重排链表
    #Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defreorderList(self,head:Optional[ListNode])->None:""&quo......
  • 链表
    链表SingleListArrayList的缺陷在熟悉并且自己写了一个ArrayList顺序表的底层架构的时候发现ArrayList是利用数组来存储数据的效率比较低:这里说两个例子在插入以及删除的时候ArrayList都需要移动剩余的元素在开始的时候设置了初始的内存后续需要扩容这里也是效率低......
  • 【Py/Java/C++三种语言OD独家2024E卷真题】20天拿下华为OD笔试之【哈希表】2024E-选修
    可上欧弟OJ系统练习华子OD、大厂真题绿色聊天软件戳oj1441了解算法冲刺训练(备注【CSDN】否则不通过)文章目录相关推荐阅读题目描述与示例题目描述输入输出示例一输入输出说明示例二输入输出说明解题思路代码pythonjavacpp时空复......
  • 算法记录——链表
    2.链表2.1判断是否是回文链表1.方法一:利用栈反转链表/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,Lis......
  • 【数据结构.总集篇】第一章 链表
    文章目录1.链表1.1线性表1.2顺序表1.3单链表链表简介单链表的介绍线性表的链式存储头节点概念为何引入头结点单链表的基本操作创建一个单链表初始化头插法尾插法删除操作打印总代码1.4单链表循环1.5双链表双链表的定义双链表上的操作初始化插入操作头插法尾插法......
  • Leetcode 706. 设计哈希映射
    1.题目基本信息1.1.题目描述不使用任何内建的哈希表库设计一个哈希映射(HashMap)。实现MyHashMap类:MyHashMap()用空映射初始化对象voidput(intkey,intvalue)向HashMap插入一个键值对(key,value)。如果key已经存在于映射中,则更新其对应的值value。intget(in......