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

缓存算法：LRU 与 LFU 原理及 Java 实现 | 极客日志

class LRUCache {
    // 1. 双向链表节点类：封装缓存的 key、value，以及前后指针
    class DLinkedNode {
        int key; // 缓存键（淘汰节点时需要通过 key 删除哈希表中的映射）
        int value; // 缓存值
        DLinkedNode prev; // 前驱节点（双向链表）
        DLinkedNode next; // 后继节点（双向链表）

        // 无参构造：用于创建哑头/哑尾节点（无实际 key/value）
        public DLinkedNode() {}

        // 有参构造：用于创建真实的缓存节点（初始化 key 和 value）
        public DLinkedNode(int _key, int _value) {
            this.key = _key;
            this.value = _value;
        }
    }

    // 2. LRUCache 核心成员变量
    private Map<Integer, DLinkedNode> cache = new HashMap<>(); // 哈希表：key -> 节点（O(1) 查找）
    private int size; // 当前缓存中的节点数量
    private int capacity; // 缓存的最大容量
    private DLinkedNode head; // 链表哑头节点（哨兵，无实际数据，简化边界）
    private DLinkedNode tail; // 链表哑尾节点（哨兵，无实际数据）

    // 3. 构造方法：初始化 LRU 缓存
    public LRUCache(int capacity) {
        this.size = 0; // 初始缓存为空，节点数为 0
        this.capacity = capacity; // 设置缓存最大容量
        head = new DLinkedNode(); // 初始化哑头节点
        tail = new DLinkedNode(); // 初始化哑尾节点
        head.next = tail; // 哑头指向哑尾，形成空链表
        tail.prev = head; // 哑尾指向哑头，双向绑定
    }

    // 4. get 操作：根据 key 获取缓存值
    public int get(int key) {
        // 步骤 1：从哈希表中查找节点
        DLinkedNode node = cache.get(key);
        // 步骤 2：key 不存在，返回 -1
        if (node == null) {
            return -1;
        }
        // 步骤 3：key 存在，将节点移到链表头部（标记为'最近使用'）
        moveToHead(node);
        // 步骤 4：返回节点的 value
        return node.value;
    }

    // 5. put 操作：添加/更新缓存
    public void put(int key, int value) {
        // 步骤 1：从哈希表查找节点
        DLinkedNode node = cache.get(key);
        // 情况 1：key 不存在，新增节点
        if (node == null) {
            // 子步骤 1.1：创建新的缓存节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 子步骤 1.2：将新节点加入哈希表
            cache.put(key, newNode);
            // 子步骤 1.3：将新节点添加到链表头部（最近使用）
            addToHead(newNode);
            // 子步骤 1.4：当前缓存节点数 +1
            size++;
            // 子步骤 1.5：若节点数超过容量，淘汰'最少使用'的节点（链表尾部）
            if (size > capacity) {
                // 移除链表尾部节点
                DLinkedNode tailNode = removeTail();
                // 同步从哈希表删除该节点的 key
                cache.remove(tailNode.key);
                // 缓存节点数 -1
                size--;
            }
        }
        // 情况 2：key 已存在，更新缓存值
        else {
            // 子步骤 2.1：更新节点的 value
            node.value = value;
            // 子步骤 2.2：将节点移到链表头部（标记为'最近使用'）
            moveToHead(node);
        }
    }

    // 6. 辅助方法：删除链表中指定的节点（O(1) 时间）
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next; // 前驱节点跳过当前节点，指向后继节点
        node.next.prev = node.prev; // 后继节点跳过当前节点，指向前驱节点
    }

    // 7. 辅助方法：将节点添加到链表头部（O(1) 时间）
    private void addToHead(DLinkedNode node) {
        node.prev = head; // 新节点的前驱指向哑头
        node.next = head.next; // 新节点的后继指向原头节点（哑头的下一个）
        head.next.prev = node; // 原头节点的前驱指向新节点
        head.next = node; // 哑头的后继指向新节点（完成头插）
    }

    // 8. 辅助方法：将节点移到链表头部（先删除，再头插）
    private void moveToHead(DLinkedNode node) {
        removeNode(node); // 先从原位置删除节点
        addToHead(node); // 再将节点添加到头部
    }

    // 9. 辅助方法：移除链表尾部的真实节点（最少使用的节点），并返回该节点
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev; // 哑尾的前驱是最后一个真实节点
        removeNode(res); // 删除该节点
        return res; // 返回被删除的节点（用于同步删除哈希表）
    }
}

部分	作用
key/value	value 存储缓存值；key 是核心 —— 淘汰节点时，需要通过 key 删除哈希表中的映射（仅存 value 无法做到）；
prev/next	双向链表的前后指针，支持 O(1) 时间的节点增删；
构造方法	无参构造用于创建哑头/哑尾（哨兵节点），有参构造用于创建真实缓存节点；

变量名	作用
cache	哈希表（HashMap），key→节点的映射，解决链表遍历查找慢的问题，实现 O(1) 查找；
size	记录当前缓存中的节点数，用于判断是否超出容量；
capacity	缓存最大容量，是淘汰逻辑的触发条件；
head/tail	哑头/哑尾节点（哨兵），避免处理'链表为空''节点是头/尾'等边界问题，让增删逻辑统一；

方法名	作用
removeNode	通用的节点删除方法，通过修改前后指针跳过目标节点，O(1) 时间完成；
addToHead	头插法：将节点添加到哑头之后（链表头部），标记为'最近使用'；
moveToHead	组合 removeNode + addToHead，实现'节点移到头部'的逻辑；
removeTail	删除链表最后一个真实节点（哑尾的前驱），返回该节点用于同步删除哈希表；

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);
        }
    }
}

部分	作用
成员变量 cnt/time	cnt 记录节点被访问的频率，time 记录最后一次访问的时间戳，是排序核心；
构造方法	初始化节点的频率、时间戳、键、值；
equals()	定义节点'相等'的规则（按 cnt+time），保证 TreeSet 能正确判断节点；
compareTo()	定义 TreeSet 的排序规则：先按频率升序，频率相同按时间戳升序，这是 LFU 核心逻辑；
hashCode()	配合 equals()，保证相等的节点哈希值相同，避免 TreeSet/HashMap 哈希冲突；

变量名	类型	作用
capacity	int	缓存的最大容量，超过容量时触发淘汰逻辑；
time	int	全局时间戳，每次访问/更新节点时递增，用于标记节点的访问顺序；
key_table	HashMap<Integer, Node>	键 -> 节点的映射，实现 O(1) 时间复杂度查找节点；
S	TreeSet	有序集合，按 compareTo() 规则排序，快速找到「待淘汰节点」（第一个元素）；

// 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;
    }
}

部分	作用
成员变量 key/val	存储缓存的键和值，淘汰时需要通过 key 删除 keyTable 中的映射；
成员变量 freq	记录该节点被访问的频率，是 freqTable 的核心索引；
成员变量 prev/next	双向链表的前后指针，实现节点的快速增删；
构造方法	无参构造用于创建哑节点（哨兵），有参构造用于创建真实缓存节点；

方法 / 变量	作用
dummyHead/dummyTail	哑头/哑尾节点（哨兵），避免处理「链表为空/只有一个节点」的边界问题；
size	记录链表节点数，快速判断链表是否为空；
addFirst(Node)	头插法：新访问的节点放链表头部（LRU 规则，最新使用的在头部）；
remove(Node)	删除指定节点：O(1) 时间复杂度，双向链表的核心优势；
getHead()	获取链表第一个真实节点（最新访问的节点）；
getTail()	获取链表最后一个真实节点（最久未使用的节点，淘汰时删这个）；

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

一、LRU 缓存算法

1. 哈希表 + 双向链表

算法思路

代码实现

代码分析

二、LFU 缓存算法

1. 哈希表 + 平衡二叉树

核心设计思路

代码实现

代码分析

2. 双哈希表

算法设计

代码实例

代码分析

三、总结

更多推荐文章

相关免费在线工具

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

一、LRU 缓存算法

1. 哈希表 + 双向链表

算法思路

代码实现

代码分析

二、LFU 缓存算法

1. 哈希表 + 平衡二叉树

核心设计思路

代码实现

代码分析

2. 双哈希表

算法设计

代码实例

代码分析

三、总结

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具