LFU算法

一、LFU 是什么

LFU（Least Frequently Used，最不经常使用）是一种缓存淘汰策略：缓存满了要腾位置时，优先踢掉访问频率最低的 key。

它和更常见的 LRU（Least Recently Used，最近最少使用）区别在于判断视角：

  • LRU 看”最近有没有被用”——久没碰的先走。
  • LFU 看”总共被用了多少次”——用得少的先走。

所以 LFU 适合”热点数据稳定”的场景：某些 key 被反复高频访问，LFU 会一直把它们留在缓存里，不会被偶发的单次访问冲掉，实现比 LRU 复杂，这里给出两种LFU实现。

二、明确几个规则

不管哪种实现，都要先定清楚淘汰的边界情况：

  1. 频率计数：每个 key 被 get 或 put（新插入算 1 次）访问一次，频率 +1。
  2. 淘汰谁：取当前所有 key 里频率最小的；如果多个 key 频率相同，按”最久没被访问”的先淘汰（同频内用 LRU 兜底）。
  3. 容量：构造函数传入 capacity，capacity <= 0 时所有写操作直接忽略。

两个实现的目标都是把 get / put 做成高效的，差异主要在”怎么存频率、怎么快速找到要淘汰的 key”。

三、版本一：自定义双向链表 + 最小频率计数（O(1)）

3.1 数据结构

维护三样东西：

字段 类型 作用
keyToNode HashMap<Integer, Node> key 直接定位到链表节点，避免扫描
freqToLists HashMap<Integer, FreqList> 频率 → 该频率下的双向链表
minFreq int 当前最小频率，淘汰时直接用它查链表

每条”频率链表”（FreqList）里挂的是该频率下所有 key 的节点，节点按访问时间排序（头新尾旧）。FreqList 内部用头尾两个哨兵节点，省掉大量空指针判断；判空直接用 head.next == tail，不额外维护 size。

节点字段说明：Node 保留 key、value、freq 三个字段。

  • key 必须留：淘汰时从频率链表尾部取出的是 Node 对象，得拿它的 key 去 keyToNode 表删对应条目，否则没法 O(1) 定位要清掉的 key。
  • freq 挂在节点上：让 touch 直接 node.freq++ 拿到旧频率就是 O(1)。如果挪到一张 keyToFreq 表里，虽然 Node 能退化成只有 key+value，但 touch 得多查一次表、还得多维护一张表，并没有更简洁——所以 O(1) 双链表版习惯把 freq 挂在节点上。

3.2 操作拆解

  • get(key)：没命中返回 -1；命中则把节点频率 +1（调 touch），返回 value。
  • put(key, value)：已存在就更新 value 并 touch；不存在且满了，从 minFreq 链表尾部淘汰一个；否则插入新节点（频率 1），并重置 minFreq = 1。
  • touch(node)（核心）：int freq = node.freq++ 记下旧频率并把节点频率 +1；从旧频率链表摘除该节点，若摘除后链表空了、且旧频率正好等于 minFreq，说明最小频率档被抽空，minFreq 上移到 freq + 1；最后头插到新频率链表。

关键点：keyToNode 直接持有节点引用，摘除/插入都是指针操作，全程不扫描，所以任意步骤都是 O(1)。

3.3 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.HashMap;
import java.util.Map;

/**
 * LFU 缓存 - 版本一：自定义双向链表 + 最小频率计数（O(1)）
 */
public class LFUCacheV1 {

    private static class Node {
        int key, value, freq = 1;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }

    // 每个频率对应一条双向链表：头尾哨兵节点
    private static class FreqList {
        Node head = new Node(-1, -1), tail = new Node(-1, -1);
        FreqList() { head.next = tail; tail.prev = head; }
        boolean isEmpty() { return head.next == tail; }
        void addFirst(Node n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }
        void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
        Node removeLast() { if (isEmpty()) return null; Node n = tail.prev; remove(n); return n; }
    }

    private final int capacity;
    private int minFreq;
    private final Map<Integer, Node> keyToNode = new HashMap<Integer, Node>();
    private final Map<Integer, FreqList> freqToLists = new HashMap<Integer, FreqList>();

    public LFUCacheV1(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = keyToNode.get(key);
        if (node == null) {
            return -1;
        }
        touch(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        Node node = keyToNode.get(key);
        if (node != null) {
            node.value = value;
            touch(node);
            return;
        }
        if (keyToNode.size() == capacity) {
            FreqList bucket = freqToLists.get(minFreq);
            Node evicted = bucket.removeLast();
            keyToNode.remove(evicted.key);
            if (bucket.isEmpty()) {
                freqToLists.remove(minFreq);
            }
        }
        Node newNode = new Node(key, value);
        keyToNode.put(key, newNode);
        freqToLists.computeIfAbsent(1, k -> new FreqList()).addFirst(newNode);
        minFreq = 1;
    }

    // 频率 +1：从旧桶摘除，插入新桶头部，并维护 minFreq。
    private void touch(Node node) {
        int freq = node.freq++;
        FreqList oldBucket = freqToLists.get(freq);
        oldBucket.remove(node);
        if (oldBucket.isEmpty()) {
            freqToLists.remove(freq);
        }
        if (freq == minFreq && oldBucket.isEmpty()) {
            minFreq = freq + 1;
        }
        freqToLists.computeIfAbsent(freq + 1, k -> new FreqList()).addFirst(node);
    }
}

四、版本二：TreeMap + LinkedHashSet（O(log n)）

如果你不在乎 O(1) 的极致，而想用 JDK 现成容器把代码写短，可以用 TreeMap + LinkedHashSet。思路更直白，复杂度 O(log n)（来自 TreeMap 的查找/插入）。

4.1 数据结构

字段 类型 作用
keyToNode HashMap<Integer, Node> key → 自定义节点（节点里存 value + freq）
freqToKeys TreeMap<Integer, LinkedHashSet<Integer>> 频率 → 该频率下的所有 key

和版本一一样用自定义 Node 承载 value 和 freq，get/put里直接node.value、node.freq取用即可。节点不存key，因为 key 就是 keyToNode` 的映射键，淘汰时拿它去删节点表就行。

巧妙点：

  • TreeMap 的 firstKey() 天然就是最小频率，不用像版本一那样手动维护 minFreq 变量。
  • 每个频率下的 key 放进 LinkedHashSet，它保持插入顺序。淘汰时取该集合迭代器的第一个元素，也就是”同频中最先进入、最久没被访问”的 key。

4.2 操作拆解

  • get(key)：命中则 touch 后返回 value，否则 -1。
  • put(key, val)：已存在就更新 value 并 touch；不存在且满了调用 evict()；否则新 key 频率置 1，塞进 freqToKeys 里频率 1 对应的集合。
  • touch(key)：从旧频率集合移除，加入新频率集合；若旧集合空了，从 TreeMap 里删掉这个频率档。
  • evict()：freqToKeys.firstKey() 拿最小频率 → 取对应集合第一个 key → 删除它，连带清掉 keyToValue / keyToFreq 记录。

“取或建频率桶”同样用 computeIfAbsent 一行搞定。

4.3 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.TreeMap;

/**
 * LFU 缓存 - 版本二：TreeMap + LinkedHashSet（O(log n)）
 */
public class LFUCacheV2 {

    private final int capacity;
    private final Map<Integer, Node> keyToNode = new java.util.HashMap<Integer, Node>();
    private final TreeMap<Integer, LinkedHashSet<Integer>> freqToKeys =
            new TreeMap<Integer, LinkedHashSet<Integer>>();

    public LFUCacheV2(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = keyToNode.get(key);
        if (node == null) {
            return -1;
        }
        touch(key, node);
        return node.value;
    }

    public void put(int key, int val) {
        if (capacity <= 0) {
            return;
        }
        Node node = keyToNode.get(key);
        if (node != null) {
            node.value = val;
            touch(key, node);
            return;
        }
        if (keyToNode.size() == capacity) {
            evict();
        }
        Node newNode = new Node(val);
        keyToNode.put(key, newNode);
        freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<Integer>()).add(key);
    }

    // 把 key 从旧频率桶移到新频率桶（频率 +1），桶空则清理该频率档。
    private void touch(int key, Node node) {
        int oldFreq = node.freq;
        LinkedHashSet<Integer> oldKeys = freqToKeys.get(oldFreq);
        oldKeys.remove(key);
        if (oldKeys.isEmpty()) {
            freqToKeys.remove(oldFreq);
        }
        node.freq = oldFreq + 1;
        freqToKeys.computeIfAbsent(node.freq, k -> new LinkedHashSet<Integer>()).add(key);
    }

    // TreeMap.firstKey() 即最小频率；取该集合最早插入的 key 淘汰。
    private void evict() {
        int minFreq = freqToKeys.firstKey();
        LinkedHashSet<Integer> keys = freqToKeys.get(minFreq);
        int evictedKey = keys.iterator().next();
        keys.remove(evictedKey);
        if (keys.isEmpty()) {
            freqToKeys.remove(minFreq);
        }
        keyToNode.remove(evictedKey);
    }

    private static final class Node {
        int value;
        int freq = 1;

        Node(int value) {
            this.value = value;
        }
    }
}

五、两种实现对比

维度 版本一（双向链表） 版本二（TreeMap）
时间复杂度 每次操作 O(1) 每次操作 O(log n)
空间复杂度 O(n) O(n)
核心容器 HashMap + 自写双向链表 HashMap + TreeMap + LinkedHashSet
最小频率获取 手动维护 minFreq 变量 TreeMap.firstKey() 直接取
同频排序 链表头尾顺序天然维护 LinkedHashSet 插入顺序维护
代码量 中等（要写链表，但 computeIfAbsent + touch 已收敛） 少（全靠现成容器，computeIfAbsent 收尾）
适合场景 高性能、面试手写、追求 O(1) 业务代码快速实现、可读性优先

一个容易踩的坑：版本二里”同频内谁先淘汰”依赖 LinkedHashSet 的插入顺序。

六、小结

  • LFU 的核心是”按累计访问频率淘汰，同频用 LRU 兜底”。
  • 版本一靠自写双向链表（FreqList）+ minFreq 变量把复杂度压到 O(1)，是标准答法；频率提升收敛成一个 touch，取/建频率桶用 computeIfAbsent 一行解决。节点保留 key/value/freq 三个字段，前两者是 O(1) 淘汰和 O(1) 频率读写的硬需求。
  • 版本二用 TreeMap 的 firstKey() 替掉手动维护最小频率，LinkedHashSet 管同频顺序，代码最短，复杂度 O(log n)，工程里图省事够用。

如果要在真实系统里用 LFU，记得补上频率衰减（比如定期把频率减半）来缓和新 key 一进来就被误杀的缓存污染问题——那是另一个话题了……

数据结构与算法
#数据结构 #算法 #LFU
LFU算法
https://zyue2022.github.io/2026/08/23/LFU算法/
作者
ZYUE
发布于
2026年8月23日
更新于
2026年8月23日
许可协议