LRU 与 LFU 缓存算法详解：原理、实现与面试要点

代码分析：

• DLinkedNode 内部类：除了存储 key 和 value，还需要 prev 和 next 指针支持 O(1) 增删。注意 key 必须存储，因为淘汰时需要通过它从哈希表中删除映射。
• 核心成员变量：cache 负责快速查找，size 和 capacity 控制容量，head 和 tail 作为哨兵简化逻辑。
• 辅助方法：removeNode 是通用的节点删除逻辑，addToHead 和 moveToHead 配合实现了 LRU 的'最近使用'机制。

二、LFU 缓存算法

LFU（Least Frequently Used）策略优先淘汰访问频率最低的元素。若频率相同，则淘汰最早访问的元素。

1. 哈希表 + 平衡二叉树

设计思路：

借助 HashMap 实现 O(1) 查找，借助 TreeSet 实现节点的有序存储（按频率 + 时间戳排序），保证淘汰操作的效率。

代码实现：

class LFUCache {
    // 缓存节点类：封装频率、时间戳、键、值，实现 Comparable 用于 TreeSet 排序
    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);
        key_table.put(key, 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);
            key_table.put(key, cache);
        }
    }
}

关键点：

• 排序规则：TreeSet 按 cnt 升序，cnt 相同则按 time 升序。第一个元素即为待淘汰节点。
• 更新逻辑：每次更新节点属性后，必须先从 TreeSet 移除旧节点，更新后再重新加入，否则排序会失效。

2. 双哈希表优化

为了进一步优化性能，可以使用双哈希表加双向链表，将所有操作的时间复杂度都控制在 O(1)。

算法设计：

• keyTable：键 → 节点的哈希表，实现 O(1) 查找。
• 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, val, freq;
        Node prev, 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, 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) 时间复杂度，是 LFU 缓存的最优实现。

• 按频率分组：每个频率对应一个双向链表，链表内按 LRU 排序。
• minfreq 快速定位：淘汰时直接取 minfreq 对应链表的尾节点。
• 频率更新：节点访问后频率 +1，从原频率链表移到新频率链表。

三、总结

LRU 和 LFU 是面试中高频考察的缓存淘汰策略。LRU 侧重于'最近使用'，适合数据访问局部性较强的场景；LFU 侧重于'历史频率'，适合某些数据长期被频繁访问的场景。掌握这两种算法的实现细节，特别是数据结构的选择与边界处理，对于应对相关面试题至关重要。