LFU 缓存淘汰算法

LRU 看“多久没被用”，LFU 看“被用了多少次”。当缓存已满时，LFU 先找访问次数最少的键；如果多个键频次相同，再淘汰其中最久没有被使用的那个。频次与新旧顺序是两条不同的线索，不能只维护其中一条。

问题与目标

以 LeetCode 460：LFU 缓存为接口约定，实现 get(key) 与 put(key, value)，要求平均时间复杂度为 O(1)。

• 新键插入后，使用频次为 1。
• 成功读取，或更新已经存在的键，频次增加 1，同时成为新频次组内最近使用的键。
• 读取不存在的键返回 -1，不能把这次失败当作访问次数。
• 容量为 0 时不能保存任何键。

三个索引各自解决什么问题

第一张哈希表从 key 找到 value、频次和链表位置，使我们能定位被访问的键。第二张哈希表从频次找到一个双向链表，链表头是最近使用，尾是最久未使用。再用 min_frequency 记录当前最小频次。

一次访问只让键从频次 f 移到 f+1：从旧链表按迭代器删除，再插入新链表头。整个过程不需要扫描其他键。

同频次时，为什么还需要顺序

容量为 2，依次插入 1、2，它们都在频次 1 的链表中，最近插入的 2 在前，1 在后。如果此时插入 3，淘汰的是 1。

如果在插入 3 前先读取 1，1 会进入频次 2。此时最低频次组只剩 2，所以淘汰 2，不是看所有键里谁更旧。

min_frequency 不需要每次扫描：访问造成最小频次桶变空时，刚被访问的键一定进入 f+1，所以最小值可以加一；插入新键后最小值必为 1。空桶及时删除，避免保留历史频次占用空间。

C++17 实现

#include <cstddef>
#include <list>
#include <unordered_map>

class LFUCache {
 public:
  explicit LFUCache(int capacity)
      : capacity_(capacity > 0 ? static_cast<std::size_t>(capacity) : 0) {}
  LFUCache(const LFUCache&) = delete;
  LFUCache& operator=(const LFUCache&) = delete;

  int get(int key) {
    auto found = entries_.find(key);
    if (found == entries_.end()) return -1;
    const int value = found->second.value;
    promote(key, found->second);
    return value;
  }

  void put(int key, int value) {
    if (capacity_ == 0) return;
    auto found = entries_.find(key);
    if (found != entries_.end()) {
      found->second.value = value;
      promote(key, found->second);
      return;
    }
    if (entries_.size() == capacity_) {
      auto& oldest_bucket = buckets_.at(min_frequency_);
      const int removed_key = oldest_bucket.back();
      oldest_bucket.pop_back();
      entries_.erase(removed_key);
      if (oldest_bucket.empty()) buckets_.erase(min_frequency_);
    }
    auto& first_bucket = buckets_[1];
    first_bucket.push_front(key);
    entries_.emplace(key, Entry{value, 1, first_bucket.begin()});
    min_frequency_ = 1;
  }

 private:
  struct Entry {
    int value;
    int frequency;
    std::list<int>::iterator position;
  };

  void promote(int key, Entry& entry) {
    const int old_frequency = entry.frequency;
    auto& old_bucket = buckets_.at(old_frequency);
    old_bucket.erase(entry.position);
    if (old_bucket.empty()) {
      buckets_.erase(old_frequency);
      if (min_frequency_ == old_frequency) ++min_frequency_;
    }
    ++entry.frequency;
    auto& new_bucket = buckets_[entry.frequency];
    new_bucket.push_front(key);
    entry.position = new_bucket.begin();
  }

  std::size_t capacity_;
  int min_frequency_ = 0;
  std::unordered_map<int, Entry> entries_;
  std::unordered_map<int, std::list<int>> buckets_;
};

这里删除拷贝操作，避免复制缓存后让记录中的链表迭代器仍指向旧对象。实现面向题目的有限操作次数，不处理频次整数无限增长、并发访问或分配失败后的强异常保证；它不是可以不加修改就投入多线程服务的生产缓存。

复杂度与边界

双向链表删除已知位置、头插和尾删都是 O(1)；哈希查找是平均 O(1)，所以正常 get、put 平均为 O(1)，不是最坏情况保证。容量为 C 时空间 O(C)，空频次桶会被清理。

测试不能只覆盖“读一下、放一个”：还需要检查同频次的 LRU 决胜、更新旧键是否增加频次、容量 0、失败读取，以及最小桶被清空后的下一次淘汰。

常见误区

LFU 不等于把频次作为排序键放进普通有序容器；那样每次操作通常要 O(log C)。仅记录频次、不记录同频次访问顺序，也无法满足本题的淘汰规则。