缓存算法：LRU 与 LFU 原理及 Java 实现

代码分析

（1）DLinkedNode 内部类（双向链表节点）

（2）LRUCache 核心成员变量

（3）核心方法

• 构造方法 LRUCache(int capacity)：初始化缓存容量、节点数，以及哑头/哑尾节点，形成一个'空的双向链表'。
• get(int key)：查哈希表 → 不存在返回 -1 → 存在则将节点移到头部 → 返回值；关键：moveToHead 保证'最近使用的节点在头部'，是 LRU 规则的核心体现。
• put(int key, int value)：分两种场景。key 不存在（新增）：创建节点 → 哈希表 + 链表头部添加 → 节点数 +1 → 超容量则删尾部节点（同步删哈希表）；key 存在（更新）：更新节点值 → 移到链表头部（标记为最近使用）。

（4）辅助方法（链表操作）

（5）总结 核心优势：哈希表（O(1) 查找）+ 双向链表（O(1) 增删），实现所有操作的 O(1) 时间复杂度，是 LRU 缓存的最优实现。 核心规则：最近使用的节点在链表头部，最少使用的在尾部；访问/更新节点 → 移到头部；新增节点 → 加在头部；超容 → 删尾部。 关键细节：哑头/哑尾简化了链表边界处理，让增删逻辑无需区分特殊情况；节点中存储 key 是淘汰时同步删除哈希表的关键。

二、LFU 缓存算法

1. 哈希表 + 平衡二叉树

核心设计思路

• 支持 get（获取缓存值）和 put（添加/更新缓存）操作；
• 当缓存容量满时，优先淘汰访问频率最低的元素；若频率相同，则淘汰最早访问（时间戳最小）的元素；
• 借助 HashMap 实现 O(1) 时间复杂度的节点查找，借助 TreeSet 实现节点的有序存储（按频率 + 时间戳排序），保证淘汰操作的效率。

代码实现

class LFUCache {
    // 缓存节点类：封装频率、时间戳、键、值，实现 Comparable 用于 TreeSet 排序
    class Node implements Comparable<Node> {
        int cnt; // 访问频率（核心排序字段 1）
        int time; // 时间戳（核心排序字段 2，频率相同时按时间戳排序）
        int key; // 缓存的键
        int value; // 缓存的值

        // 节点构造方法：初始化所有属性
        Node(int cnt, int time, int key, int value) {
            this.cnt = cnt;
            this.time = time;
            this.key = key;
            this.value = value;
        }

        // 重写 equals：判断两个节点是否相等（按频率 + 时间戳）
        // 用于 TreeSet 判断节点是否存在
        public boolean equals(Object anObject) {
            if (this == anObject) { // 引用相同，直接相等
                return true;
            }
            if (anObject instanceof Node) { // 类型匹配时，比较 cnt 和 time
                Node rhs = (Node) anObject;
                return this.cnt == rhs.cnt && this.time == rhs.time;
            }
            return false;
        }

        // 重写 compareTo：定义 TreeSet 的排序规则
        // 核心逻辑：先按频率升序，频率相同则按时间戳升序
        // 这样 TreeSet 的第一个元素就是「频率最低、最早访问」的节点（待淘汰）
        public int compareTo(Node rhs) {
            return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
        }

        // 重写 hashCode：保证 equals 相等的节点哈希值相同
        // 避免 TreeSet/HashMap 出现哈希冲突
        public int hashCode() {
            return cnt * 1000000007 + time; // 用大质数乘，减少哈希碰撞
        }
    }

    // 缓存核心成员变量
    int capacity; // 缓存最大容量
    int time; // 全局时间戳：每次访问/更新节点时递增，标记访问顺序
    Map<Integer, Node> key_table; // 哈希表：key -> Node，O(1) 查找节点
    TreeSet<Node> S; // 有序集合：按「频率 + 时间戳」排序，快速找到待淘汰节点

    // LFU 缓存构造方法：初始化容量、时间戳、哈希表、有序集合
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.time = 0;
        key_table = new HashMap<>();
        S = new TreeSet<>();
    }

    // get 操作：根据 key 获取缓存值
    public int get(int key) {
        // 边界 1：缓存容量为 0，直接返回 -1
        if (capacity == 0) {
            return -1;
        }
        // 边界 2：key 不存在于缓存，返回 -1
        if (!key_table.containsKey(key)) {
            return -1;
        }
        // 步骤 1：取出旧节点（此时节点的 cnt/time 是旧值）
        Node cache = key_table.get(key);
        // 步骤 2：从 TreeSet 移除旧节点（因为节点属性要更新，排序位置会变）
        S.remove(cache);
        // 步骤 3：更新节点属性：访问频率 +1，时间戳递增
        cache.cnt++;
        cache.time = ++time;
        // 步骤 4：将更新后的节点重新加入 TreeSet（重新排序）
        S.add(cache);
        // 步骤 5：更新哈希表中的节点（虽然引用没变，但属性已更新，可省略，但写了更严谨）
        key_table.put(key, cache);
        // 步骤 6：返回缓存值
        return cache.value;
    }

    // put 操作：添加/更新缓存
    public void put(int key, int value) {
        // 边界 1：缓存容量为 0，直接返回
        if (capacity == 0) {
            return;
        }
        // 情况 1：key 不存在，需要新增节点
        if (!key_table.containsKey(key)) {
            // 子情况 1.1：缓存已满，先淘汰「频率最低、最早访问」的节点
            if (key_table.size() == capacity) {
                // 移除 TreeSet 中第一个节点（排序最靠前，待淘汰）
                key_table.remove(S.first().key);
                S.remove(S.first());
            }
            // 子情况 1.2：创建新节点（初始频率 1，时间戳递增）
            Node cache = new Node(1, time++, key, value);
            // 加入哈希表和有序集合
            key_table.put(key, cache);
            S.add(cache);
        }
        // 情况 2：key 已存在，更新节点值 + 频率 + 时间戳
        else {
            // 步骤 1：取出旧节点
            Node cache = key_table.get(key);
            // 步骤 2：从 TreeSet 移除旧节点
            S.remove(cache);
            // 步骤 3：更新节点属性：频率 +1、时间戳递增、值更新
            cache.cnt++;
            cache.time = ++time;
            cache.value = value;
            // 步骤 4：重新加入 TreeSet
            S.add(cache);
            // 步骤 5：更新哈希表（可省略，引用不变）
            key_table.put(key, cache);
        }
    }
}

代码分析

（1）Node 内部类（核心数据结构）

（2）缓存类成员变量

（3）核心方法

• 构造方法 LFUCache(int capacity)：初始化缓存容量、全局时间戳、哈希表 key_table、有序集合 S，为后续操作做准备。
• get(int key)：边界校验：容量为 0/key 不存在，返回 -1；存在则先移除旧节点（因为属性要更新，排序位置会变）；更新节点的频率和时间戳，重新加入有序集合；返回节点的值。
• put(int key, int value)：分两种情况。key 不存在：若缓存已满，先淘汰 TreeSet 第一个节点（频率最低 + 最早访问），再创建新节点（初始频率为 1）加入哈希表和有序集合；key 已存在：和 get 逻辑类似，更新节点的频率、时间戳、值，重新加入有序集合。

（4）总结 核心逻辑：通过 HashMap 实现 O(1) 查找，通过 TreeSet 实现节点按「频率 + 时间戳」有序存储，保证 LFU 淘汰规则； 排序规则：TreeSet 按「频率升序、时间戳升序」排序，第一个元素就是待淘汰的节点； 关键操作：每次更新节点（get/put）时，必须先从 TreeSet 移除旧节点，更新属性后重新加入，否则排序会失效。

2. 双哈希表

算法设计

• 双层哈希表 + 双向链表：
  • keyTable：键→节点的哈希表，实现 O(1) 时间查找节点；
  • freqTable：频率→双向链表的哈希表，同一频率的所有节点存在同一个双向链表中；
  • 双向链表内按 LRU 规则排序（新访问的节点放链表头部，淘汰时删尾部）；
• minfreq 优化：记录当前最小访问频率，直接定位「待淘汰节点所在的频率组」，无需遍历所有频率；
• 淘汰规则：缓存满时，删除 minfreq 对应链表的尾节点（该频率下最久未使用的节点）；
• 频率更新规则：节点被访问（get/put）时，频率 +1，从原频率链表移除，加入新频率链表；若原频率链表为空，则删除该频率映射，且更新 minfreq（仅当原频率 = minfreq 时）。

代码实例

// LFU 缓存核心类
class LFUCache {
    // 核心成员变量
    int minfreq; // 记录当前最小访问频率（快速定位待淘汰的频率组）
    int capacity; // 缓存最大容量
    Map<Integer, Node> keyTable; // 哈希表：key -> Node，O(1) 查找节点
    Map<Integer, DoublyLinkedList> freqTable; // 哈希表：频率 -> 双向链表（存储该频率的所有节点）

    // 构造方法：初始化 LFU 缓存
    public LFUCache(int capacity) {
        this.minfreq = 0; // 初始最小频率为 0
        this.capacity = capacity; // 设置缓存容量
        keyTable = new HashMap<>(); // 初始化 key 映射表
        freqTable = new HashMap<>(); // 初始化频率映射表
    }

    // get 操作：根据 key 获取缓存值
    public int get(int key) {
        // 边界 1：缓存容量为 0，直接返回 -1
        if (capacity == 0) {
            return -1;
        }
        // 边界 2：key 不存在于缓存，返回 -1
        if (!keyTable.containsKey(key)) {
            return -1;
        }
        // 步骤 1：从 keyTable 取出目标节点
        Node node = keyTable.get(key);
        int val = node.val; // 缓存值
        int freq = node.freq; // 节点当前访问频率
        // 步骤 2：从原频率对应的链表中移除该节点
        freqTable.get(freq).remove(node);
        // 步骤 3：检查原频率链表是否为空，若空则删除该频率映射，并更新 minfreq
        if (freqTable.get(freq).size == 0) {
            freqTable.remove(freq); // 删除空链表的频率映射
            // 只有当原频率等于当前 minfreq 时，才需要更新 minfreq（因为该频率组已空）
            if (minfreq == freq) {
                minfreq += 1;
            }
        }
        // 步骤 4：将节点加入「频率 +1」对应的链表（新频率组）
        // 若频率 +1 的链表不存在，则新建空链表
        DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
        list.addFirst(new Node(key, val, freq + 1)); // 新节点加入链表头部（LRU 规则：新访问的放头部）
        freqTable.put(freq + 1, list); // 更新频率映射表
        keyTable.put(key, freqTable.get(freq + 1).getHead()); // 更新 key 映射表（指向新节点）
        // 步骤 5：返回缓存值
        return val;
    }

    // put 操作：添加/更新缓存
    public void put(int key, int value) {
        // 边界 1：缓存容量为 0，直接返回
        if (capacity == 0) {
            return;
        }
        // 情况 1：key 不存在，需要新增节点
        if (!keyTable.containsKey(key)) {
            // 子情况 1.1：缓存已满，先淘汰「最小频率组中最久未使用」的节点
            if (keyTable.size() == capacity) {
                // 找到 minfreq 对应的链表，取其尾节点（最久未使用）
                Node node = freqTable.get(minfreq).getTail();
                keyTable.remove(node.key); // 从 keyTable 删除该节点
                freqTable.get(minfreq).remove(node); // 从频率链表删除该节点
                // 若删除后链表为空，删除该频率的映射
                if (freqTable.get(minfreq).size == 0) {
                    freqTable.remove(minfreq);
                }
            }
            // 子情况 1.2：创建新节点（初始频率为 1），加入频率 1 的链表
            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()); // 更新 key 映射表
            minfreq = 1; // 新增节点的频率为 1，重置 minfreq 为 1
        }
        // 情况 2：key 已存在，更新节点值 + 频率（逻辑和 get 操作基本一致）
        else {
            // 步骤 1：取出旧节点
            Node node = keyTable.get(key);
            int freq = node.freq; // 旧频率
            // 步骤 2：从原频率链表移除旧节点
            freqTable.get(freq).remove(node);
            // 步骤 3：检查原频率链表是否为空，更新 minfreq（同 get 逻辑）
            if (freqTable.get(freq).size == 0) {
                freqTable.remove(freq);
                if (minfreq == freq) {
                    minfreq += 1;
                }
            }
            // 步骤 4：创建新节点（更新值 + 频率 +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());
        }
    }
}

// 双向链表节点类：封装 key、value、频率，以及前后指针
class Node {
    int key; // 缓存键
    int val; // 缓存值
    int freq; // 访问频率
    Node prev; // 前驱节点（双向链表）
    Node next; // 后继节点（双向链表）

    // 无参构造：默认键 -1、值 -1、频率 0（用于创建哑节点）
    Node() {
        this(-1, -1, 0);
    }

    // 有参构造：初始化键、值、频率
    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; // 初始节点数为 0
    }

    // 头插法：将节点添加到链表头部（新访问的节点放头部，符合 LRU 规则）
    public void addFirst(Node node) {
        Node prevHead = dummyHead.next; // 原链表第一个真实节点
        node.prev = dummyHead; // 新节点前驱指向哑头
        dummyHead.next = node; // 哑头后继指向新节点
        node.next = prevHead; // 新节点后继指向原头节点
        prevHead.prev = node; // 原头节点前驱指向新节点
        size++; // 节点数 +1
    }

    // 删除指定节点（支持任意位置的节点删除）
    public void remove(Node node) {
        Node prev = node.prev; // 待删节点的前驱
        Node next = node.next; // 待删节点的后继
        prev.next = next; // 前驱指向后继，跳过待删节点
        next.prev = prev; // 后继指向前驱，跳过待删节点
        size--; // 节点数 -1
    }

    // 获取链表第一个真实节点（最新访问的节点）
    public Node getHead() {
        return dummyHead.next;
    }

    // 获取链表最后一个真实节点（最久未使用的节点，淘汰时删这个）
    public Node getTail() {
        return dummyTail.prev;
    }
}

代码分析

（1）Node 类（双向链表节点）

（2）DoublyLinkedList 类（双向链表）

（3）LFUCache 核心类

• 成员变量
  • minfreq：记录当前最小访问频率，核心优化点：无需遍历所有频率，直接定位待淘汰的频率组；
  • capacity：缓存最大容量，超过时触发淘汰逻辑；
  • keyTable：键→节点的映射，O(1) 时间查找节点，是缓存快速访问的基础；
  • freqTable：频率→链表的映射，将同一频率的节点分组，实现「按频率淘汰」的核心逻辑；
• 构造方法：初始化所有成员变量，为缓存操作做准备；minfreq 初始为 0，因为还没有任何节点。
• get(int key) 方法（获取缓存）：边界校验：容量为 0/key 不存在 → 返回 -1；取出节点，记录其值和当前频率；从原频率链表移除节点，若链表为空则删除该频率映射，并更新 minfreq；将节点（频率 +1）加入新频率链表的头部；更新 keyTable 映射，返回缓存值。
• put(int key, int value) 方法（添加/更新缓存）：分两种核心场景。场景 1：key 不存在（新增节点）：缓存已满：删除 minfreq 对应链表的尾节点（最久未使用），再新增节点；缓存未满：直接创建频率为 1 的新节点，加入频率 1 的链表，重置 minfreq=1；场景 2：key 已存在（更新节点）：逻辑和 get 基本一致，唯一区别是更新节点的 value 值；

（4）总结 核心优势：相比 TreeSet 实现，该方案所有操作（增删改查）都是纯 O(1) 时间复杂度（TreeSet 的增删是 O(logn)），是 LFU 缓存的最优实现； 核心逻辑：按频率分组：每个频率对应一个双向链表，链表内按 LRU 排序；minfreq 快速定位：淘汰时直接取 minfreq 对应链表的尾节点；频率更新：节点访问后频率 +1，从原频率链表移到新频率链表； 关键细节：哑节点简化链表边界处理；头插法保证链表内 LRU 规则；只有原频率 = minfreq 且链表为空时，才更新 minfreq。

三、总结

本文主要介绍了面试中常考的缓存算法问题 LRU 和 LFU，包括思路分析和代码的实现与分析。