面试高频缓存算法：LRU 与 LFU 原理及 Java 实现

实现细节分析

• DLinkedNode：除了存值，必须存 key。因为淘汰时需要通过 key 从哈希表中删除映射，仅存 value 无法反向查找。
• 辅助方法：removeNode 是通用的 O(1) 删除；addToHead 负责头插；moveToHead 组合两者，确保访问过的节点立刻变为'最近使用'。
• 复杂度：所有操作均为 O(1)。

二、LFU 缓存算法

1. 哈希表 + 平衡二叉树

核心思路 LFU（Least Frequently Used）优先淘汰访问频率最低的元素。若频率相同，则淘汰最早访问的。 借助 HashMap 实现 O(1) 查找，借助 TreeSet 按「频率 + 时间戳」排序，保证淘汰效率。

代码实现

class LFUCache {
    class Node implements Comparable<Node> {
        int cnt;
        int time;
        int key;
        int value;

        public Node(int cnt, int time, int key, int value) {
            this.cnt = cnt;
            this.time = time;
            this.key = key;
            this.value = value;
        }

        @Override
        public boolean equals(Object anObject) {
            if (this == anObject) return true;
            if (anObject instanceof Node) {
                Node rhs = (Node) anObject;
                return this.cnt == rhs.cnt && this.time == rhs.time;
            }
            return false;
        }

        @Override
        public int compareTo(Node rhs) {
            return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
        }

        @Override
        public int hashCode() {
            return cnt * 1000000007 + time;
        }
    }

    private int capacity;
    private int time;
    private Map<Integer, Node> key_table;
    private TreeSet<Node> S;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.time = 0;
        key_table = new HashMap<>();
        S = new TreeSet<>();
    }

    public int get(int key) {
        if (capacity == 0 || !key_table.containsKey(key)) {
            return -1;
        }
        Node cache = key_table.get(key);
        S.remove(cache);
        cache.cnt++;
        cache.time = ++time;
        S.add(cache);
        return cache.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (!key_table.containsKey(key)) {
            if (key_table.size() == capacity) {
                key_table.remove(S.first().key);
                S.remove(S.first());
            }
            Node cache = new Node(1, time++, key, value);
            key_table.put(key, cache);
            S.add(cache);
        } else {
            Node cache = key_table.get(key);
            S.remove(cache);
            cache.cnt++;
            cache.time = ++time;
            cache.value = value;
            S.add(cache);
        }
    }
}

注意 每次更新节点属性后，必须先移除旧节点再重新加入 TreeSet，否则排序会失效。此方案增删复杂度为 O(log n)。

2. 双哈希表优化

为了达到纯 O(1) 复杂度，可以使用双层哈希表 + 双向链表。

• keyTable：键 → 节点，用于查找。
• freqTable：频率 → 双向链表，同一频率的节点存在同一个链表中。
• minfreq：记录当前最小访问频率，直接定位待淘汰组。

代码实现

class LFUCache {
    private int minfreq;
    private int capacity;
    private Map<Integer, Node> keyTable;
    private Map<Integer, DoublyLinkedList> freqTable;

    public LFUCache(int capacity) {
        this.minfreq = 0;
        this.capacity = capacity;
        keyTable = new HashMap<>();
        freqTable = new HashMap<>();
    }

    public int get(int key) {
        if (capacity == 0 || !keyTable.containsKey(key)) {
            return -1;
        }
        Node node = keyTable.get(key);
        int val = node.val;
        int freq = node.freq;
        freqTable.get(freq).remove(node);
        if (freqTable.get(freq).size == 0) {
            freqTable.remove(freq);
            if (minfreq == freq) {
                minfreq += 1;
            }
        }
        DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
        list.addFirst(new Node(key, val, freq + 1));
        freqTable.put(freq + 1, list);
        keyTable.put(key, freqTable.get(freq + 1).getHead());
        return val;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (!keyTable.containsKey(key)) {
            if (keyTable.size() == capacity) {
                Node node = freqTable.get(minfreq).getTail();
                keyTable.remove(node.key);
                freqTable.get(minfreq).remove(node);
                if (freqTable.get(minfreq).size == 0) {
                    freqTable.remove(minfreq);
                }
            }
            DoublyLinkedList list = freqTable.getOrDefault(1, new DoublyLinkedList());
            list.addFirst(new Node(key, value, 1));
            freqTable.put(1, list);
            keyTable.put(key, freqTable.get(1).getHead());
            minfreq = 1;
        } else {
            Node node = keyTable.get(key);
            int freq = node.freq;
            freqTable.get(freq).remove(node);
            if (freqTable.get(freq).size == 0) {
                freqTable.remove(freq);
                if (minfreq == freq) {
                    minfreq += 1;
                }
            }
            DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
            list.addFirst(new Node(key, value, freq + 1));
            freqTable.put(freq + 1, list);
            keyTable.put(key, freqTable.get(freq + 1).getHead());
        }
    }

    class Node {
        int key;
        int val;
        int freq;
        Node prev;
        Node next;

        public Node() { this(-1, -1, 0); }
        public Node(int key, int val, int freq) {
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }

    class DoublyLinkedList {
        Node dummyHead;
        Node dummyTail;
        int size;

        public DoublyLinkedList() {
            dummyHead = new Node();
            dummyTail = new Node();
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
            size = 0;
        }

        public void addFirst(Node node) {
            Node prevHead = dummyHead.next;
            node.prev = dummyHead;
            dummyHead.next = node;
            node.next = prevHead;
            prevHead.prev = node;
            size++;
        }

        public void remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            size--;
        }

        public Node getHead() { return dummyHead.next; }
        public Node getTail() { return dummyTail.prev; }
    }
}

总结 相比 TreeSet 方案，双哈希表方案所有操作均为 O(1)。核心在于按频率分组，利用 minfreq 快速定位淘汰目标，并在频率更新时动态调整链表归属。

三、总结

LRU 适合关注近期访问热点的场景，LFU 适合关注长期访问频率的场景。面试中重点考察对数据结构组合的理解，特别是如何平衡查找速度与淘汰策略的效率。掌握哨兵节点的使用能显著减少边界条件的判断逻辑。