LRUCache

LRU

最近最少使用置换算法。

有一个容量capacity，需要支持插入一个(key, value)，按照key查找value。

插入：

• 不在cache中：
  • 还有容量，直接插入到末尾
  • 没有容量，就挤掉开头最旧的，再插入到末尾
• 在cache中：
  • 移动到末尾

查找：

• 不在cache中：
  • 返回-1
• 在cache中：
  • 移动到末尾

核心：用双向链表按序维护所有value，以支持快速删除操作；用哈希表维护所有key到链表节点的映射，用于快速查找操作。

注意list中必须key和value都存，因为替换的时候，得把替换掉的元素从unordered_map中移除。

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

    int get(int key) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            int value = it->second->second;
            lst.erase(it->second);
            it->second = lst.emplace(lst.end(), key, value);
            return value;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            lst.erase(it->second);
            it->second = lst.emplace(lst.end(), key, value);
        } else if (lst.size() < cap) {
            pos.emplace(key, lst.emplace(lst.end(), key, value));
        } else {
            pos.erase(lst.begin()->first);
            lst.pop_front();
            pos.emplace(key, lst.emplace(lst.end(), key, value));
        }
    }

private:
    unordered_map<int, list<pair<int, int>>::iterator> pos;
    list<pair<int, int>> lst;
    int cap;
};

优化

处理预读问题：在读取时，由于局部性原理，会预读连续的若干页，但这些页可能并不会真正需要读取。

解决方案：构造两级链表。预读先放到一级，真正读取时再从一级移到二级；二级中被淘汰的再放回一级。

处理偶发的批量读问题：有时会连续读取若干页，但读取这一次后就不再使用，此时会污染整个二级链表。

解决方案：提高从一级链表移到二级链表的门槛，比如第二次读才能移过去。

扩展

增加过期时间。

线程安全。

LFU

最不常使用替换算法。需要维护被访问次数，如果有多个访问次数最少的，则退化为LRU，选择最近访问时间最老的。