LRU 缓存算法

看到 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，哈希表将无法删除。