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

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

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 演示 LinkedHashMap 如何用 accessOrder + removeEldestEntry 实现 LRU。
 *
 * 理论：docs/00-foundations/04-lru-cache-and-eviction-policies.md
 *
 * 运行：
 * cd labs/foundations/cache-eviction-demo
 * javac -d out src/LruLinkedHashMapDemo.java
 * java -cp out LruLinkedHashMapDemo
 */
public class LruLinkedHashMapDemo {

    static final int MAX_ENTRIES = 3;

    public static void main(String[] args) {
        System.out.println("====== LinkedHashMap 实现 LRU（容量 = " + MAX_ENTRIES + "）======\n");
        System.out.println("规则：accessOrder=true → 迭代顺序 = 最久未用 → 最近使用");
        System.out.println("      put 后若 size > MAX，removeEldestEntry 删掉链表头（最久未用）\n");

        LruMap<String, String> lru = new LruMap<>();

        step(lru, "put A", () -> lru.put("A", "apple"));
        step(lru, "put B", () -> lru.put("B", "banana"));
        step(lru, "put C", () -> lru.put("C", "cherry"));
        step(lru, "put D（满员，应踢 A）", () -> lru.put("D", "date"));
        step(lru, "get B（B 变最近使用）", () -> lru.get("B"));
        step(lru, "put E（应踢 C，因 B 刚被访问、C 最久）", () -> lru.put("E", "elderberry"));

        System.out.println("====== 续：D-B-E 后反复 get D，再 put F ======\n");
        for (int i = 0; i < 5; i++) {
            lru.get("D");
        }
        step(lru, "get D ×5（D 已在队尾，顺序不变）", () -> {
        });
        step(lru, "put F（应踢 B，不是 D）", () -> lru.put("F", "fig"));

        System.out.println("\n====== 手写 LRU：HashMap + 双向链表（见 SimpleLruCache.java）======\n");
        System.out.println("运行: java -cp out SimpleLruCache");
        System.out.println();

        System.out.println("====== 对比：accessOrder=false（插入顺序，不是 LRU）======\n");
        demoInsertionOrderNotLru();
    }

    static void step(LruMap<String, String> lru, String action, Runnable op) {
        System.out.println("--- " + action + " ---");
        op.run();
        System.out.println("  当前 key 顺序（左=最久未用，右=最近使用）: " + lru.orderKeys());
        System.out.println("  当前 map: " + lru);
        System.out.println();
    }

    /** accessOrder=false 时，「最老」= 最早插入，get 不会把条目挪到尾部 */
    static void demoInsertionOrderNotLru() {
        LinkedHashMap<String, String> fifoStyle = new LinkedHashMap<>(16, 0.75f, false) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > MAX_ENTRIES;
            }
        };
        fifoStyle.put("A", "1");
        fifoStyle.put("B", "2");
        fifoStyle.put("C", "3");
        fifoStyle.get("A");
        fifoStyle.put("D", "4");
        System.out.println("put A,B,C → get A → put D");
        System.out.println("  淘汰的是链表头（最早插入）: 剩 " + fifoStyle.keySet());
        System.out.println("  若先 get 的是 C，put D 仍会踢 A —— 与「按访问」的 LRU 行为不同");
    }

    static class LruMap<K, V> extends LinkedHashMap<K, V> {
        LruMap() {
            super(16, 0.75f, true);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            boolean evict = size() > MAX_ENTRIES;
            if (evict) {
                System.out.println("  >> removeEldestEntry: 淘汰最久未用 key=" + eldest.getKey());
            }
            return evict;
        }

        String orderKeys() {
            return entrySet().stream()
                    .map(e -> String.valueOf(e.getKey()))
                    .collect(Collectors.joining(" → "));
        }
    }
}