LRU 缓存（LeetCode 146）

题目要求

实现 LRU（最近最少使用）缓存，get 和 put 均为 O(1)。

• get(key)：若 key 存在，返回 value 并标记为最近使用；否则返回 -1
• put(key, value)：插入/更新 key-value；若超容量，淘汰最久未使用的

核心设计

• HashMap：O(1) 定位节点
• 双向链表：O(1) 在任意位置删除节点，并维护访问顺序（头=最新，尾=最旧）

head <-> 新节点 <-> ... <-> 旧节点 <-> tail

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // 哑头
    private final Node tail = new Node(0, 0);   // 哑尾

    static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

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

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToFront(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToFront(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToFront(node);
            if (map.size() > capacity) {
                Node removed = removeLast();
                map.remove(removed.key);
            }
        }
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

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

    private void moveToFront(Node node) {
        remove(node);
        addToFront(node);
    }

    private Node removeLast() {
        Node node = tail.prev;
        remove(node);
        return node;
    }
}

Java 内置 LinkedHashMap 版（工程替代方案）

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);   // accessOrder=true
        this.capacity = capacity;
    }

    public int get(int key) { return super.getOrDefault(key, -1); }

    public void put(int key, int value) { super.put(key, value); }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

工程中优先掌握手写双向链表版，内置版作为补充说明。

LFU 缓存（LeetCode 460）

LFU（最不频繁使用）：淘汰使用次数最少的；频次相同时淘汰最久未用的。

class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, Integer> keyVal = new HashMap<>();     // key -> val
    private final Map<Integer, Integer> keyFreq = new HashMap<>();    // key -> freq
    private final Map<Integer, LinkedHashSet<Integer>> freqKeys = new HashMap<>();  // freq -> keys（有序）

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

    public int get(int key) {
        if (!keyVal.containsKey(key)) return -1;
        increaseFreq(key);
        return keyVal.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (keyVal.containsKey(key)) {
            keyVal.put(key, value);
            increaseFreq(key);
        } else {
            if (keyVal.size() >= capacity) removeMinFreq();
            keyVal.put(key, value);
            keyFreq.put(key, 1);
            freqKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        }
    }

    private void increaseFreq(int key) {
        int freq = keyFreq.get(key);
        keyFreq.put(key, freq + 1);
        freqKeys.get(freq).remove(key);
        if (freqKeys.get(freq).isEmpty()) {
            freqKeys.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        freqKeys.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void removeMinFreq() {
        LinkedHashSet<Integer> keys = freqKeys.get(minFreq);
        int evict = keys.iterator().next();   // 最久未用的
        keys.remove(evict);
        if (keys.isEmpty()) freqKeys.remove(minFreq);
        keyVal.remove(evict);
        keyFreq.remove(evict);
    }
}

三个 HashMap 记住：keyVal, keyFreq, freqKeys（频次→有序key集合）。