【数据结构与算法】LRU Cache 算法实现

admin管理员组

文章数量:1440442

【数据结构与算法】LRU Cache 算法实现

Ⅰ. 什么是 LRU Cache

​ LRU（ Least Recently Used） 是一种淘汰策略的缩写，意思是 最近最少使用，它是一种 Cache 替换算法。

​ 什么是 Cache ？狭义的 Cache 指的是位于 CPU 和主存间的快速 RAM， 通常它不像系统主存那样使用 DRAM 技术，而使用昂贵但较快速的 SRAM 技术。 广义上的 Cache 指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了 CPU 与主存之间有 Cache， 内存与硬盘之间也有 Cache，乃至在硬盘与网络之间也有某种意义上的 Cache ── 称为 Internet 临时文件夹或网络内容缓存等。

​ Cache 的容量有限，因此当 Cache 的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。 LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU 译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

Ⅱ. LRU Cache 的实现

​ 实现 LRU Cache 的方法和思路很多，但是要保持高效实现 O(1) 的 put 和 get，那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为 双向链表可以实现任意位置 O(1) 的插入和删除，使用 哈希表可以实现 O(1) 的查找。

​ 这分别对应到 stl 中的 list 和 unordered_map ，其中要注意的是，为了能达到 O(1) 的效果，我们在 unordered_map 中存放的 value 值是 list 的迭代器 list<int, int>::iterator ，这样子就能快速找到链表中每个节点。

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
• 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

代码语言：javascript代码运行次数：0运行复制

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示： 1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 105

代码实现：

代码语言：javascript代码运行次数：0运行复制

class LRUCache {
public:
    LRUCache(int capacity) 
        :_capacity(capacity)
    {}
    
    int get(int key) 
    {
        auto it = _hashMap.find(key);
        if(it == _hashMap.end())
        {
            return -1;
        }
        else
        {
            // 存在的话，先要将其更新到链表的首位，有两种方法
            // 1、使用 push_front + erase 但是容易迭代器失效问题
            // 2、使用 splice 函数进行转移
            // 这里采用第二种方法
            _LRUList.splice(_LRUList.begin(), _LRUList, it->second);

            return it->second->second;
        }
    }
    
    void put(int key, int value) 
    {
        auto it = _hashMap.find(key);
        if(it == _hashMap.end())
        {
            // 找不到说明要新增
            // 需要判断一下是否需要逐出LRU
            if(_capacity == _hashMap.size())
            {
                // 删掉LRU
                _hashMap.erase(_LRUList.back().first);
                _LRUList.pop_back();
            }

            // 插入新增元素，记得哈希表也要存
            _LRUList.push_front(make_pair(key, value));
            _hashMap.insert(make_pair(key, _LRUList.begin()));
        }
        else
        {
            // 找到的话则更新到链表头并修改value即可
            it->second->second = value;
            _LRUList.splice(_LRUList.begin(), _LRUList, it->second);
        }
    }
private:
    // 容量是为了判断是否已经满了
    size_t _capacity;

    // 哈希表为查找、更新时提供O(1)的时间复杂度
    typedef list<pair<int, int>>::iterator LTiter;
    unordered_map<int, LTiter> _hashMap;

    // 双向链表提供O(1)的插入
    list<pair<int, int>> _LRUList;
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-12，如有侵权请联系 cloudcommunity@tencent 删除前往查看链表数据结构与算法算法缓存int

本文标签： 数据结构与算法LRU Cache 算法实现