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

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

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

/**
 * 手写 LRU：HashMap + 双向链表，不依赖 LinkedHashMap。
 *
 * 链表方向约定（与 printOrder 一致）：
 * head … 最久未用(LRU，先淘汰) … 最近使用(MRU) … tail
 * - 淘汰：从 head.next 移除
 * - 插入/访问：linkBefore(tail, node)
 *
 * 理论：docs/00-foundations/04-lru-cache-and-eviction-policies.md
 *
 * 运行：
 * cd labs/foundations/cache-eviction-demo
 * javac -d out src/SimpleLruCache.java && java -cp out SimpleLruCache
 */
public class SimpleLruCache {

    static final int CAPACITY = 3;

    public static void main(String[] args) {
        System.out.println("====== 手写 LRU（HashMap + 双向链表）======\n");

        SimpleLruCache cache = new SimpleLruCache(CAPACITY);

        cache.put("A", "apple");
        cache.put("B", "banana");
        cache.put("C", "cherry");
        cache.printOrder("put A,B,C");

        cache.put("D", "date");
        cache.printOrder("put D（踢最左 A）");

        cache.get("B");
        cache.printOrder("get B（moveToTail）");

        for (int i = 0; i < 5; i++) {
            cache.get("D");
        }
        cache.printOrder("get D ×5（已在队尾，顺序不变）");

        cache.put("F", "fig");
        cache.printOrder("put F（踢最左 C，不是 D）");
    }

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

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

    private final int capacity;
    private final Map<String, Node> map = new HashMap<>();
    /**
     * 哑头 / 哑尾：不存真实数据，只作哨兵，方便头尾 O(1) 插删。
     * head 侧 = 最久未用，满员时 evict head.next；
     * tail 侧 = 最近使用，新 put / get 命中后都接到 tail 前。
     */
    private final Node head = new Node("", "");
    private final Node tail = new Node("", "");

    SimpleLruCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

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

    /** 已存在：更新并挪到 tail（算使用）；新 key：插到 tail 前，满员则踢 head.next */
    void put(String key, String value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToTail(node);
            return;
        }
        Node created = new Node(key, value);
        map.put(key, created);
        linkBefore(tail, created);
        if (map.size() > capacity) {
            Node eldest = head.next;
            unlink(eldest);
            map.remove(eldest.key);
            System.out.println("  >> evict LRU key=" + eldest.key);
        }
    }

    void moveToTail(Node node) {
        unlink(node);
        linkBefore(tail, node);
    }

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

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

    void printOrder(String label) {
        StringBuilder sb = new StringBuilder();
        for (Node p = head.next; p != tail; p = p.next) {
            if (sb.length() > 0) {
                sb.append(" → ");
            }
            sb.append(p.key);
        }
        System.out.println(label + " | 顺序（左=最久未用）: " + sb);
    }
}