一、LRU 缓存算法
1.哈希表 + 双向链表
1.题目链接：LRU 缓存
2.题目描述：
3.算法思路：
1.双向链表 + 哈希表 组合：
双向链表（带哑头 / 哑尾节点）：维护缓存节点的访问顺序，最近使用的节点放在链表头部，最少使用的节点放在链表尾部（淘汰时直接删尾部）；
哈希表（cache）：实现 key 到节点的 O (1) 快速查找，解决链表遍历查找慢的问题；
2.哑头 / 哑尾节点：简化链表边界处理（无需判断'节点是否为头 / 尾''链表是否为空'等特殊情况）；
3.核心规则：
访问 / 更新节点（get/ 更新式 put）：将节点移到链表头部（标记为'最近使用'）；
新增节点：添加到链表头部，若缓存容量超限，删除链表尾部节点（最少使用），并同步删除哈希表中的映射。
4.代码实现：
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; // 返回被删除的节点（用于同步删除哈希表）
}
}
- 代码分析：
（1）DLinkedNode 内部类（双向链表节点）：
| 部分 | 作用 |
|---|---|
| key/value | value 存储缓存值；key 是核心 —— 淘汰节点时，需要通过 key 删除哈希表中的映射（仅存 value 无法做到）； |
| prev/next | 双向链表的前后指针，支持 O (1) 时间的节点增删； |
| 构造方法 | 无参构造用于创建哑头 / 哑尾（哨兵节点），有参构造用于创建真实缓存节点； |
（2）LRUCache 核心成员变量
| 变量名 | 作用 |
|---|---|
| cache | 哈希表（HashMap），key→节点 的映射，解决链表遍历查找慢的问题，实现 O (1) 查找； |
| size | 记录当前缓存中的节点数，用于判断是否超出容量； |
| capacity | 缓存最大容量，是淘汰逻辑的触发条件； |
| head/tail | 哑头 / 哑尾节点（哨兵），避免处理'链表为空''节点是头 / 尾'等边界问题，让增删逻辑统一； |
（3）核心方法：
构造方法 LRUCache(int capacity)
初始化缓存容量、节点数，以及哑头 / 哑尾节点，形成一个'空的双向链表'（哑头→哑尾，哑尾→哑头）。
get(int key)（获取缓存）
核心逻辑：查哈希表 → 不存在返回 -1 → 存在则将节点移到头部 → 返回值；
关键：moveToHead 保证'最近使用的节点在头部'，是 LRU 规则的核心体现。
put(int key, int value)（添加 / 更新缓存）
分两种场景：
key 不存在（新增）：创建节点 → 哈希表 + 链表头部添加 → 节点数 +1 → 超容量则删尾部节点（同步删哈希表）；
key 存在（更新）：更新节点值 → 移到链表头部（标记为最近使用）；
关键：新增节点必加在头部，超容时删尾部（最少使用），完全符合 LRU 淘汰规则。
（4）辅助方法（链表操作）
| 方法名 | 作用 |
|---|---|
| removeNode | 通用的节点删除方法，通过修改前后指针跳过目标节点，O (1) 时间完成； |
| addToHead | 头插法：将节点添加到哑头之后（链表头部），标记为'最近使用'； |
| moveToHead | 组合 removeNode + addToHead，实现'节点移到头部'的逻辑； |
| removeTail | 删除链表最后一个真实节点（哑尾的前驱），返回该节点用于同步删除哈希表； |
（5）总结：
核心优势：哈希表（O (1) 查找）+ 双向链表（O (1) 增删），实现所有操作的 O (1) 时间复杂度，是 LRU 缓存的最优实现；
核心规则：
最近使用的节点在链表头部，最少使用的在尾部；
访问 / 更新节点 → 移到头部；新增节点 → 加在头部；超容 → 删尾部；
关键细节：
哑头 / 哑尾简化了链表边界处理，让增删逻辑无需区分特殊情况；
节点中存储 key 是淘汰时同步删除哈希表的关键（仅存 value 无法反向查找 key）
二、LFU 缓存算法
1.题目链接：LFU 缓存
2.题目描述：
1、哈希表 + 平衡二叉树
1.核心设计思路：
支持 get（获取缓存值）和 put（添加 / 更新缓存）操作；
当缓存容量满时，优先淘汰访问频率最低的元素；若频率相同，则淘汰最早访问（时间戳最小）的元素；
借助 HashMap 实现 O (1) 时间复杂度的节点查找，借助 TreeSet 实现节点的有序存储（按频率 + 时间戳排序），保证淘汰操作的效率。
2.代码实现：
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);
}
}
}
3.代码分析：
（1）Node 内部类（核心数据结构）
| 部分 | 作用 |
|---|---|
| 成员变量 cnt/time | cnt 记录节点被访问的频率，time 记录最后一次访问的时间戳，是排序核心； |
| 构造方法 | 初始化节点的频率、时间戳、键、值； |
| equals() | 定义节点'相等'的规则（按 cnt+time），保证 TreeSet 能正确判断节点； |
| compareTo() | 定义 TreeSet 的排序规则：先按频率升序，频率相同按时间戳升序，这是 LFU 核心逻辑； |
| hashCode() | 配合 equals()，保证相等的节点哈希值相同，避免 TreeSet/HashMap 哈希冲突； |
（2）缓存类成员变量
| 变量名 | 类型 | 作用 |
|---|---|---|
| capacity | int | 缓存的最大容量，超过容量时触发淘汰逻辑； |
| time | int | 全局时间戳，每次访问 / 更新节点时递增，用于标记节点的访问顺序； |
| key_table | HashMap<Integer, Node> | 键 -> 节点的映射，实现 O (1) 时间复杂度查找节点； |
| S | TreeSet | 有序集合，按 compareTo() 规则排序，快速找到「待淘汰节点」（第一个元素）； |
（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 缓存核心类
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; // 链表当前节点数
// 构造方法：初始化空双向链表
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;
}
}
3.代码分析：
（1）Node 类（双向链表节点）
| 部分 | 作用 |
|---|---|
| 成员变量 key/val | 存储缓存的键和值，淘汰时需要通过 key 删除 keyTable 中的映射； |
| 成员变量 freq | 记录该节点被访问的频率，是 freqTable 的核心索引； |
| 成员变量 prev/next | 双向链表的前后指针，实现节点的快速增删； |
| 构造方法 | 无参构造用于创建哑节点（哨兵），有参构造用于创建真实缓存节点； |
（2）DoublyLinkedList 类（双向链表）
| 方法 / 变量 | 作用 |
|---|---|
| dummyHead/dummyTail | 哑头 / 哑尾节点（哨兵），避免处理「链表为空 / 只有一个节点」的边界问题； |
| size | 记录链表节点数，快速判断链表是否为空； |
| addFirst(Node) | 头插法：新访问的节点放链表头部（LRU 规则，最新使用的在头部）； |
| remove(Node) | 删除指定节点：O (1) 时间复杂度，双向链表的核心优势； |
| getHead() | 获取链表第一个真实节点（最新访问的节点）； |
| getTail() | 获取链表最后一个真实节点（最久未使用的节点，淘汰时删这个）； |
（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。
