【缓存算法】一篇文章带你彻底搞懂面试高频题LRU/LFU

系列文章目录

文章目录

• 系列文章目录
• 一、LRU缓存算法
  • 1.哈希表 + 双向链表
• 二、LFU缓存算法
  • 1、哈希表 + 平衡二叉树
  • 2、双哈希表
• 三、总结

一、LRU缓存算法

1.哈希表 + 双向链表

1.题目链接：LRU缓存
2.题目描述：

3.算法思路：

1.双向链表 + 哈希表 组合：
双向链表（带哑头 / 哑尾节点）：维护缓存节点的访问顺序，最近使用的节点放在链表头部，最少使用的节点放在链表尾部（淘汰时直接删尾部）；
哈希表（cache）：实现 key 到节点的 O (1) 快速查找，解决链表遍历查找慢的问题；
2.哑头 / 哑尾节点：简化链表边界处理（无需判断 “节点是否为头 / 尾”“链表是否为空” 等特殊情况）；
3.核心规则：
访问 / 更新节点（get/ 更新式 put）：将节点移到链表头部（标记为 “最近使用”）；
新增节点：添加到链表头部，若缓存容量超限，删除链表尾部节点（最少使用），并同步删除哈希表中的映射。

4.代码实现：

classLRUCache{// 1. 双向链表节点类：封装缓存的key、value，以及前后指针classDLinkedNode{int key;// 缓存键（淘汰节点时需要通过key删除哈希表中的映射）int value;// 缓存值DLinkedNode prev;// 前驱节点（双向链表）DLinkedNode next;// 后继节点（双向链表）// 无参构造：用于创建哑头/哑尾节点（无实际key/value）publicDLinkedNode(){}// 有参构造：用于创建真实的缓存节点（初始化key和value）publicDLinkedNode(int _key,int _value){this.key = _key;this.value = _value;}}// 2. LRUCache核心成员变量privateMap<Integer,DLinkedNode> cache =newHashMap<>();// 哈希表：key -> 节点（O(1)查找）privateint size;// 当前缓存中的节点数量privateint capacity;// 缓存的最大容量privateDLinkedNode head;// 链表哑头节点（哨兵，无实际数据，简化边界）privateDLinkedNode tail;// 链表哑尾节点（哨兵，无实际数据）// 3. 构造方法：初始化LRU缓存publicLRUCache(int capacity){this.size =0;// 初始缓存为空，节点数为0this.capacity = capacity;// 设置缓存最大容量 head =newDLinkedNode();// 初始化哑头节点 tail =newDLinkedNode();// 初始化哑尾节点 head.next = tail;// 哑头指向哑尾，形成空链表 tail.prev = head;// 哑尾指向哑头，双向绑定}// 4. get操作：根据key获取缓存值publicintget(int key){// 步骤1：从哈希表中查找节点DLinkedNode node = cache.get(key);// 步骤2：key不存在，返回-1if(node ==null){return-1;}// 步骤3：key存在，将节点移到链表头部（标记为“最近使用”）moveToHead(node);// 步骤4：返回节点的valuereturn node.value;}// 5. put操作：添加/更新缓存publicvoidput(int key,int value){// 步骤1：从哈希表查找节点DLinkedNode node = cache.get(key);// 情况1：key不存在，新增节点if(node ==null){// 子步骤1.1：创建新的缓存节点DLinkedNode newNode =newDLinkedNode(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)时间）privatevoidremoveNode(DLinkedNode node){ node.prev.next = node.next;// 前驱节点跳过当前节点，指向后继节点 node.next.prev = node.prev;// 后继节点跳过当前节点，指向前驱节点}// 7. 辅助方法：将节点添加到链表头部（O(1)时间）privatevoidaddToHead(DLinkedNode node){ node.prev = head;// 新节点的前驱指向哑头 node.next = head.next;// 新节点的后继指向原头节点（哑头的下一个） head.next.prev = node;// 原头节点的前驱指向新节点 head.next = node;// 哑头的后继指向新节点（完成头插）}// 8. 辅助方法：将节点移到链表头部（先删除，再头插）privatevoidmoveToHead(DLinkedNode node){removeNode(node);// 先从原位置删除节点addToHead(node);// 再将节点添加到头部}// 9. 辅助方法：移除链表尾部的真实节点（最少使用的节点），并返回该节点privateDLinkedNoderemoveTail(){DLinkedNode res = tail.prev;// 哑尾的前驱是最后一个真实节点removeNode(res);// 删除该节点return res;// 返回被删除的节点（用于同步删除哈希表）}}

5. 代码分析：

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

（2） LRUCache 核心成员变量

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

关键：新增节点必加在头部，超容时删尾部（最少使用），完全符合 LRU 淘汰规则。
（4） 辅助方法（链表操作）

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

二、LFU缓存算法

1.题目链接：LFU缓存
2.题目描述：

1、哈希表 + 平衡二叉树

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

classLFUCache{// 缓存节点类：封装频率、时间戳、键、值，实现Comparable用于TreeSet排序classNodeimplementsComparable<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判断节点是否存在publicbooleanequals(Object anObject){if(this== anObject){// 引用相同，直接相等returntrue;}if(anObject instanceofNode){// 类型匹配时，比较cnt和timeNode rhs =(Node) anObject;returnthis.cnt == rhs.cnt &&this.time == rhs.time;}returnfalse;}// 重写compareTo：定义TreeSet的排序规则// 核心逻辑：先按频率升序，频率相同则按时间戳升序// 这样TreeSet的第一个元素就是「频率最低、最早访问」的节点（待淘汰）publicintcompareTo(Node rhs){return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;}// 重写hashCode：保证equals相等的节点哈希值相同// 避免TreeSet/HashMap出现哈希冲突publicinthashCode(){return cnt *1000000007+ time;// 用大质数乘，减少哈希碰撞}}// 缓存核心成员变量int capacity;// 缓存最大容量int time;// 全局时间戳：每次访问/更新节点时递增，标记访问顺序Map<Integer,Node> key_table;// 哈希表：key -> Node，O(1)查找节点TreeSet<Node>S;// 有序集合：按「频率+时间戳」排序，快速找到待淘汰节点// LFU缓存构造方法：初始化容量、时间戳、哈希表、有序集合publicLFUCache(int capacity){this.capacity = capacity;this.time =0; key_table =newHashMap<>();S=newTreeSet<>();}// get操作：根据key获取缓存值publicintget(int key){// 边界1：缓存容量为0，直接返回-1if(capacity ==0){return-1;}// 边界2：key不存在于缓存，返回-1if(!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操作：添加/更新缓存publicvoidput(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 =newNode(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：重新加入TreeSetS.add(cache);// 步骤5：更新哈希表（可省略，引用不变） key_table.put(key, cache);}}}

3.代码分析：
（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、双哈希表

1.算法设计：
双层哈希表 + 双向链表：
keyTable：键→节点的哈希表，实现 O (1) 时间查找节点；
freqTable：频率→双向链表的哈希表，同一频率的所有节点存在同一个双向链表中；
双向链表内按 LRU 规则排序（新访问的节点放链表头部，淘汰时删尾部）；

minfreq 优化：记录当前最小访问频率，直接定位「待淘汰节点所在的频率组」，无需遍历所有频率；

淘汰规则：缓存满时，删除 minfreq 对应链表的尾节点（该频率下最久未使用的节点）；

频率更新规则：节点被访问（get/put）时，频率 + 1，从原频率链表移除，加入新频率链表；若原频率链表为空，则删除该频率映射，且更新 minfreq（仅当原频率 = minfreq 时）。
2.代码实例：

// LFU缓存核心类classLFUCache{// 核心成员变量int minfreq;// 记录当前最小访问频率（快速定位待淘汰的频率组）int capacity;// 缓存最大容量Map<Integer,Node> keyTable;// 哈希表：key -> Node，O(1)查找节点Map<Integer,DoublyLinkedList> freqTable;// 哈希表：频率 -> 双向链表（存储该频率的所有节点）// 构造方法：初始化LFU缓存publicLFUCache(int capacity){this.minfreq =0;// 初始最小频率为0this.capacity = capacity;// 设置缓存容量 keyTable =newHashMap<Integer,Node>();// 初始化key映射表 freqTable =newHashMap<Integer,DoublyLinkedList>();// 初始化频率映射表}// get操作：根据key获取缓存值publicintget(int key){// 边界1：缓存容量为0，直接返回-1if(capacity ==0){return-1;}// 边界2：key不存在于缓存，返回-1if(!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：检查原频率链表是否为空，若空则删除该频率映射，并更新minfreqif(freqTable.get(freq).size ==0){ freqTable.remove(freq);// 删除空链表的频率映射// 只有当原频率等于当前minfreq时，才需要更新minfreq（因为该频率组已空）if(minfreq == freq){ minfreq +=1;}}// 步骤4：将节点加入「频率+1」对应的链表（新频率组）// 若频率+1的链表不存在，则新建空链表DoublyLinkedList list = freqTable.getOrDefault(freq +1,newDoublyLinkedList()); list.addFirst(newNode(key, val, freq +1));// 新节点加入链表头部（LRU规则：新访问的放头部） freqTable.put(freq +1, list);// 更新频率映射表 keyTable.put(key, freqTable.get(freq +1).getHead());// 更新key映射表（指向新节点）// 步骤5：返回缓存值return val;}// put操作：添加/更新缓存publicvoidput(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,newDoublyLinkedList()); list.addFirst(newNode(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,newDoublyLinkedList()); list.addFirst(newNode(key, value, freq +1));// 新节点放头部 freqTable.put(freq +1, list); keyTable.put(key, freqTable.get(freq +1).getHead());}}}// 双向链表节点类：封装key、value、频率，以及前后指针classNode{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;}}// 双向链表类：封装链表操作（头插、删除节点、获取头尾节点），带哑节点（简化边界处理）classDoublyLinkedList{Node dummyHead;// 哑头节点（链表头部哨兵，避免空指针）Node dummyTail;// 哑尾节点（链表尾部哨兵）int size;// 链表当前节点数// 构造方法：初始化空双向链表DoublyLinkedList(){ dummyHead =newNode();// 初始化哑头 dummyTail =newNode();// 初始化哑尾 dummyHead.next = dummyTail;// 哑头指向哑尾 dummyTail.prev = dummyHead;// 哑尾指向哑头 size =0;// 初始节点数为0}// 头插法：将节点添加到链表头部（新访问的节点放头部，符合LRU规则）publicvoidaddFirst(Node node){Node prevHead = dummyHead.next;// 原链表第一个真实节点 node.prev = dummyHead;// 新节点前驱指向哑头 dummyHead.next = node;// 哑头后继指向新节点 node.next = prevHead;// 新节点后继指向原头节点 prevHead.prev = node;// 原头节点前驱指向新节点 size++;// 节点数+1}// 删除指定节点（支持任意位置的节点删除）publicvoidremove(Node node){Node prev = node.prev;// 待删节点的前驱Node next = node.next;// 待删节点的后继 prev.next = next;// 前驱指向后继，跳过待删节点 next.prev = prev;// 后继指向前驱，跳过待删节点 size--;// 节点数-1}// 获取链表第一个真实节点（最新访问的节点）publicNodegetHead(){return dummyHead.next;}// 获取链表最后一个真实节点（最久未使用的节点，淘汰时删这个）publicNodegetTail(){return dummyTail.prev;}}

3.代码分析：
（1）Node 类（双向链表节点）

（3）LFUCache 核心类
成员变量

构造方法
初始化所有成员变量，为缓存操作做准备；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，包括思路分析和代码的实现与分析。感谢各位能够看到最后，如有问题，欢迎各位大佬在评论区指正，希望大家可以有所收获！创作不易，希望大家多多支持