手写 LFU 缓存

手写 LFU 缓存

使用频率桶和桶内 LRU 实现平均 O(1) LFU，并解决相同频率时的确定性淘汰。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

---

一、学习目标

• 在 O(1) 内提升频率
• 用 LRU 打破同频平局
• 维护 min_frequency 不变量

---

二、前置条件

完成 LRU 缓存，熟悉双层哈希索引。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

---

三、问题与设计选择

键索引保存值、频率和桶内迭代器；频率到键链表的索引保存同频访问顺序。命中时从 f 桶移到 f+1 桶。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

---

四、内存布局与核心不变量

min_frequency 等于非空最小频率桶；每个键只存在于自身频率桶；同桶尾部最久未使用。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

---

五、核心实现

void touch(typename index_type::iterator item) {
    const auto old_frequency = item->second.frequency;
    auto& old_bucket = buckets_[old_frequency];
    old_bucket.erase(item->second.position);
    if (old_bucket.empty()) {
        buckets_.erase(old_frequency);
        if (min_frequency_ == old_frequency) ++min_frequency_;
    }
    auto& next = buckets_[old_frequency + 1];
    next.push_front(item->first);
    item->second.frequency++;
    item->second.position = next.begin();
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

---

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

template<class Key, class Value, class Hash = std::hash<Key>>
class lfu_cache {
    struct entry {
        Value value;
        std::size_t frequency{1};
        typename std::list<Key>::iterator position;
    };
    std::size_t capacity_;
    std::size_t min_frequency_{};
    std::unordered_map<Key, entry, Hash> entries_;
    std::unordered_map<std::size_t, std::list<Key>> buckets_;

    void touch(typename std::unordered_map<Key, entry, Hash>::iterator found) {
        const std::size_t old_frequency = found->second.frequency;
        auto& old_bucket = buckets_.at(old_frequency);
        old_bucket.erase(found->second.position);
        if (old_bucket.empty()) {
            buckets_.erase(old_frequency);
            if (min_frequency_ == old_frequency) ++min_frequency_;
        }
        auto& next = buckets_[old_frequency + 1];
        next.push_front(found->first);
        found->second.frequency++;
        found->second.position = next.begin();
    }
public:
    explicit lfu_cache(std::size_t capacity) : capacity_(capacity) {}
    std::size_t size() const noexcept { return entries_.size(); }
    std::size_t capacity() const noexcept { return capacity_; }
    bool contains(const Key& key) const { return entries_.contains(key); }
    std::optional<Value> get(const Key& key) {
        auto found = entries_.find(key);
        if (found == entries_.end()) return std::nullopt;
        Value result = found->second.value;
        touch(found);
        return result;
    }
    bool erase(const Key& key) {
        auto found = entries_.find(key);
        if (found == entries_.end()) return false;
        auto frequency = found->second.frequency;
        auto& bucket = buckets_.at(frequency);
        bucket.erase(found->second.position);
        entries_.erase(found);
        if (bucket.empty()) buckets_.erase(frequency);
        if (entries_.empty()) min_frequency_ = 0;
        else if (!buckets_.contains(min_frequency_)) {
            min_frequency_ = entries_.begin()->second.frequency;
            for (const auto& [unused, value] : entries_)
                min_frequency_ = std::min(min_frequency_, value.frequency);
        }
        return true;
    }
    void put(Key key, Value value) {
        if (capacity_ == 0) return;
        if (auto found = entries_.find(key); found != entries_.end()) {
            found->second.value = std::move(value);
            touch(found);
            return;
        }
        if (entries_.size() == capacity_) {
            const Key victim = buckets_.at(min_frequency_).back();
            erase(victim);
        }
        auto& bucket = buckets_[1];
        bucket.push_front(key);
        entries_.emplace(
            std::move(key),
            entry{std::move(value), 1, bucket.begin()}
        );
        min_frequency_ = 1;
    }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

---

七、使用示例与输出

预期输出或状态：

容量 2，A 命中两次、B 命中一次，再插入 C 时淘汰 B；同频时淘汰更久未访问者。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

---

八、复杂度与失效规则

操作	复杂度	说明
get	平均 O(1)	频率加一
put	平均 O(1)	新键频率一
evict	平均 O(1)	最小频率桶尾
erase	平均 O(1)	维护空桶

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

---

九、异常安全与资源管理

• 获取资源后立即交给 RAII 对象或明确记录已构造数量。
• 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
• 只有在所有后续步骤不会失败时才修改不可回滚的链接。
• 析构、释放和关闭路径不得抛异常。
• 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

---

十、常见错误

1. 只记录计数导致无法 O(1) 找最小频率

只记录计数导致无法 O(1) 找最小频率会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 空桶后不更新 min_frequency

空桶后不更新 min_frequency会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 长期热点频率无限增长

长期热点频率无限增长会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. LFU 为什么需要桶内 LRU？
2. 频率老化如何避免历史污染？
3. LFU 与 LRU 分别偏好什么工作集？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

---

十二、练习与自测

1. 增加频率衰减
2. 处理计数溢出
3. 与 LRU 比较阶段性热点轨迹

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

---

十三、官方资料与延伸阅读

• C++20 工作草案 N4861
• C++ Core Guidelines

---

上一篇：手写 LRU 缓存 ｜ 下一篇：手写 TTL 缓存