源码：labs/foundations/cache-eviction-demo/src/SimpleLfuCache.java

• 原始路径：labs/foundations/cache-eviction-demo/src/SimpleLfuCache.java
• 类型：java

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

/**
 * 手写 LFU：按访问次数淘汰；同频率时淘汰最久未用的（频率桶内 LRU）。
 *
 * 理论：docs/00-foundations/04-lru-cache-and-eviction-policies.md
 *
 * 运行：
 * cd labs/foundations/cache-eviction-demo
 * javac -d out src/SimpleLfuCache.java && java -cp out SimpleLfuCache
 */
public class SimpleLfuCache {

    static final int CAPACITY = 3;

    public static void main(String[] args) {
        System.out.println("====== 手写 LFU（频率 + 同频 LRU tie-break）======\n");

        SimpleLfuCache cache = new SimpleLfuCache(CAPACITY);

        cache.put("A", "1");
        cache.put("B", "2");
        cache.put("C", "3");
        cache.printState("put A,B,C（频率均为 1）");

        cache.get("A");
        cache.get("A");
        cache.get("A");
        cache.printState("get A ×3 → A.freq=4");

        cache.get("B");
        cache.printState("get B ×1 → B.freq=2");

        cache.put("D", "4");
        cache.printState("put D（满员：踢 freq 最小的 C，不是 A）");

        System.out.println("\n====== 与 LRU 对比 ======\n");
        System.out.println("LRU：get D 一百次 ≈ get D 一次（只更新「最近」位置）");
        System.out.println("LFU：get A 三次后 A 更难被淘汰（频率更高）");
    }

    static class Node {
        final String key;
        String value;
        int freq;
        Node prev;
        Node next;

        Node(String key, String value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
        }
    }

    static class FreqList {
        final Node head = new Node("", "");
        final Node tail = new Node("", "");

        FreqList() {
            head.next = tail;
            tail.prev = head;
        }

        void addToHead(Node node) {
            linkAfter(head, node);
        }

        boolean isEmpty() {
            return head.next == tail;
        }

        Node removeEldest() {
            Node eldest = tail.prev;
            if (eldest == head) {
                return null;
            }
            unlink(eldest);
            return eldest;
        }
    }

    private final int capacity;
    private final Map<String, Node> keyTable = new HashMap<>();
    private final Map<Integer, FreqList> freqTable = new HashMap<>();
    private int minFreq;

    SimpleLfuCache(int capacity) {
        this.capacity = capacity;
    }

    String get(String key) {
        Node node = keyTable.get(key);
        if (node == null) {
            return null;
        }
        increaseFreq(node);
        return node.value;
    }

    void put(String key, String value) {
        if (capacity <= 0) {
            return;
        }
        Node node = keyTable.get(key);
        if (node != null) {
            node.value = value;
            increaseFreq(node);
            return;
        }
        if (keyTable.size() >= capacity) {
            FreqList list = freqTable.get(minFreq);
            Node evicted = list.removeEldest();
            if (evicted != null) {
                keyTable.remove(evicted.key);
                System.out.println("  >> evict LFU key=" + evicted.key + " freq=" + evicted.freq);
            }
            if (list.isEmpty()) {
                freqTable.remove(minFreq);
            }
        }
        Node created = new Node(key, value);
        keyTable.put(key, created);
        freqBucket(1).addToHead(created);
        minFreq = 1;
    }

    void increaseFreq(Node node) {
        int oldFreq = node.freq;
        FreqList oldList = freqBucket(oldFreq);
        unlink(node);
        if (oldList.isEmpty()) {
            freqTable.remove(oldFreq);
            if (minFreq == oldFreq) {
                minFreq = oldFreq + 1;
            }
        }
        node.freq = oldFreq + 1;
        freqBucket(node.freq).addToHead(node);
    }

    FreqList freqBucket(int freq) {
        return freqTable.computeIfAbsent(freq, f -> new FreqList());
    }

    static void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    static void linkAfter(Node anchor, Node node) {
        node.prev = anchor;
        node.next = anchor.next;
        anchor.next.prev = node;
        anchor.next = node;
    }

    void printState(String label) {
        System.out.println("--- " + label + " ---");
        System.out.print("  keyTable: ");
        keyTable.forEach((k, n) -> System.out.print(k + "(f=" + n.freq + ") "));
        System.out.println();
        System.out.println("  minFreq=" + minFreq);
        System.out.println();
    }
}