5

LRU 缓存算法

 2 years ago
source link: https://murphypei.github.io/blog/2021/07/lru.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

LRU 缓存算法

发表于

2021-07-07

更新于 2021-09-06 分类于 Algorithm

阅读次数： 104 本文字数： 2.2k 阅读时长 ≈ 4 分钟

看到 lc 上有一道题是设计 LRU 算法，简单了解了一下作为记录。

LRU 算法实际上是让你设计数据结构：首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。

注意哦，get 和 put 方法必须都是 O(1) 的时间复杂度，我们举个具体例子来看看 LRU 算法怎么工作。

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)

cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

我们分析一下这个实现要求。查询和插入都需要 O(1)，那不用说了，只能是哈希表。C++ 可以用 std::unordered_map 实现。再看这个缓存满的时候，需要删除最久为使用的，所以每个元素必须在每次操作之后保持其顺序。这个实现比较灵活了，但是因为涉及 O(1) 插入，所以 std::list 是最合适的。总结：

  • 通过 key 查询和插入 O(1)，哈希表，但是哈希表无顺序。
  • 链表可保持顺序，插入和删除 O(1)，但是查询慢。

因此就需要将二者结合使用，也就是哈希链表。具体实现如下：

#include <list>
#include <unordered_map>

class LRUCache
{
public:
    LRUCache(int capacity) : capacity(capacity) {}

int get(int key)
    {
        if (hashTable.find(key) == hashTable.end())
        {
            return -1;
        }
        else
        {
            // 更新到表头
            auto iter = hashTable[key]; // 找到对应地址
            cache.splice(cache.begin(), cache, iter); // 移动到表头
            return cache.begin()->second;
        }
    }

void put(int key, int value)
    {
        if (hashTable.find(key) == hashTable.end())
        {
            if (cache.size() == capacity)
            {
                // 删除表尾
                hashTable.erase(cache.back().first);
                cache.pop_back();
            }
            // 在表头添加
            cache.push_front(std::make_pair(key, value));
            hashTable[key] = cache.begin();
        }
        else
        {
            auto iter    = hashTable[key];
            iter->second = value; // 更新元素
            cache.splice(cache.begin(), cache, iter); // 移动到表头
            hashTable[key] = cache.begin(); // 更新地址
        }
    }

private:
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hashTable;
    std::list<std::pair<int, int>>                                    cache; // key, value
    int                                                               capacity = 0;
};

具体操作就很简单了，无非是哈希表和链表的查询、删除和移动。主要看成员变量 hashTable 和 cache。cache 保存的就是实际数据的 key 和 value，hashTable 保存链表的 key 和地址。

通过哈希表，我们能够弥补链表查询慢的特点，直取链表中 key 所在节点的位置。而通过链表，我们可以很容易的维持每次操作后元素的顺序。这里有一个需要注意的，链表中必须也存有 key，因为哈希表删除是需要 key 的，链表如果只能提供 value，哈希表将无法删除。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK