每日算法 — 使用java实现LFU缓存：频率链表与哈希表协同淘汰策略

算法背景

LFU（Least Frequently Used，最不经常使用）缓存是计算机系统中经典的缓存淘汰策略。与LRU（最近最少使用）基于时间局部性不同，LFU基于频率局部性——认为被访问次数越多的数据越重要。LFU在数据库缓存、CDN内容分发、搜索引擎热点查询等场景中表现优异，因为它能有效识别真正的”热点数据”而非仅”最近数据”。

LeetCode 460题要求设计并实现一个满足O(1)时间复杂度的LFU缓存，这是数据结构设计中的高难度题目，需要巧妙结合双向链表、哈希表和频率桶结构。

核心思路

LFU的核心挑战在于：当缓存满时需要淘汰访问频率最低的数据，如果多个数据频率相同则淘汰最久未使用的。

三层数据结构：
1. keyToNode 哈希表：O(1)通过key找到节点
2. freqToList 哈希表：O(1)通过频率找到该频率下的所有节点（双向链表）
3. minFreq：记录当前最小频率，O(1)知道淘汰哪个频率桶

访问操作：
– 获取节点后，将其从旧频率链表移除，加入新频率链表
– 如果旧频率链表变空且等于minFreq，则minFreq++

插入操作：
– 新节点频率为1，加入freq=1的链表
– minFreq重置为1

淘汰操作：
– 直接淘汰minFreq对应链表的尾部节点（最久未使用）

完整Java实现

import java.util.HashMap;
import java.util.Map;

/**
 * LFU缓存 - 最不经常使用缓存淘汰策略
 * get和put操作时间复杂度均为O(1)
 */
public class LFUCache {

    // 双向链表节点
    static class Node {
        int key, value, freq;
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1; // 新节点频率为1
        }
    }

    // 双向链表（同一频率的节点集合）
    static class DoublyLinkedList {
        Node head, tail;
        int size;

        DoublyLinkedList() {
            head = new Node(0, 0); // 哨兵头节点
            tail = new Node(0, 0); // 哨兵尾节点
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        // 在链表头部添加节点（最新使用）
        void addToHead(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            size++;
        }

        // 移除指定节点
        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }

        // 移除尾部节点（最久未使用）
        Node removeTail() {
            if (size == 0) return null;
            Node node = tail.prev;
            remove(node);
            return node;
        }

        boolean isEmpty() {
            return size == 0;
        }
    }

    private final int capacity;
    private int minFreq;                    // 当前最小频率
    private final Map<Integer, Node> keyToNode;      // key -> node
    private final Map<Integer, DoublyLinkedList> freqToList; // freq -> list

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyToNode = new HashMap<>();
        this.freqToList = new HashMap<>();
    }

    public int get(int key) {
        if (!keyToNode.containsKey(key)) {
            return -1;
        }
        Node node = keyToNode.get(key);
        increaseFreq(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;

        if (keyToNode.containsKey(key)) {
            // 更新已有节点
            Node node = keyToNode.get(key);
            node.value = value;
            increaseFreq(node);
            return;
        }

        // 新节点，检查是否需要淘汰
        if (keyToNode.size() >= capacity) {
            evict();
        }

        // 创建新节点，频率为1
        Node newNode = new Node(key, value);
        keyToNode.put(key, newNode);
        freqToList.computeIfAbsent(1, k -> new DoublyLinkedList()).addToHead(newNode);
        minFreq = 1; // 新节点频率为1，最小频率重置
    }

    /**
     * 增加节点频率
     */
    private void increaseFreq(Node node) {
        int freq = node.freq;
        DoublyLinkedList oldList = freqToList.get(freq);
        oldList.remove(node);

        // 如果旧频率链表为空且是当前最小频率，更新minFreq
        if (oldList.isEmpty() && freq == minFreq) {
            minFreq++;
        }

        // 加入新频率链表
        node.freq++;
        freqToList.computeIfAbsent(freq + 1, k -> new DoublyLinkedList()).addToHead(node);
    }

    /**
     * 淘汰最小频率中最久未使用的节点
     */
    private void evict() {
        DoublyLinkedList list = freqToList.get(minFreq);
        Node removed = list.removeTail();
        if (removed != null) {
            keyToNode.remove(removed.key);
        }
    }

    public void printStatus() {
        System.out.println("缓存状态: size=" + keyToNode.size() + ", minFreq=" + minFreq);
        for (Map.Entry<Integer, DoublyLinkedList> entry : freqToList.entrySet()) {
            System.out.print("  freq=" + entry.getKey() + ": ");
            Node cur = entry.getValue().head.next;
            while (cur != entry.getValue().tail) {
                System.out.print("[" + cur.key + "=" + cur.value + "] ");
                cur = cur.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        System.out.println("=== LFU缓存测试 ===\n");

        LFUCache cache = new LFUCache(3);

        // 插入三个元素
        cache.put(1, 10);
        cache.put(2, 20);
        cache.put(3, 30);
        System.out.println("插入1,2,3后:");
        cache.printStatus();

        // 访问1和2各两次，3不访问
        cache.get(1);
        cache.get(1);
        cache.get(2);
        cache.get(2);
        System.out.println("\n访问1两次、2两次后:");
        cache.printStatus();

        // 插入4，应该淘汰频率最低的3
        cache.put(4, 40);
        System.out.println("\n插入4(淘汰频率最低的3)后:");
        cache.printStatus();

        // 访问4一次，频率变为2
        cache.get(4);
        System.out.println("\n访问4一次后:");
        cache.printStatus();

        // 插入5，此时minFreq=1的链表为空，最小频率是2
        // 淘汰频率2中最久未使用的（1或2）
        cache.put(5, 50);
        System.out.println("\n插入5后:");
        cache.printStatus();

        // 验证get
        System.out.println("\nget(1)=" + cache.get(1));
        System.out.println("get(3)=" + cache.get(3)); // 已被淘汰
    }
}

复杂度分析

总空间复杂度为O(capacity)，因为缓存最多存储capacity个节点。

LFU vs LRU 对比

LFU的冷启动问题：新数据频率为1，容易被快速淘汰。解决方案是引入”老化机制”，定期衰减所有频率计数。

扩展思考

1. 频率衰减：每隔一段时间将所有频率减半，避免历史热点长期占据缓存。
2. W-TinyLFU：Caffeine缓存使用的现代LFU变体，结合窗口LFU和分段LRU，在真实工作负载上表现更优。
3. 分布式LFU：在分布式缓存中，需要合并各节点的访问频率统计，可用Gossip协议或集中式计数器。