设计
LRU 淘汰算法
LRU（Least Recently Used，最近最少使用）是一种基于访问时间的缓存淘汰算法，核心思想是：淘汰最久未被访问的元素，优先保留近期访问的数据。
一、LRU 核心原理
为了让 Get（查询）和 Put（插入 / 更新）操作的时间复杂度都达到 O(1)，LRU 通常采用 「哈希表 + 双向链表」 的组合：
| 结构 | 作用 | 说明 |
|---|---|---|
| 哈希表 | 快速查找 key 对应的节点 | Key: 缓存 key，Value: 指向双向链表节点的指针 |
| 双向链表 | 维护访问顺序 | 链表头部：最近访问的节点 链表尾部：最久未访问的节点 淘汰时直接删除尾部节点 |
二、代码实现
// Node 双向链表节点
type Node struct {
key int // 缓存 key（淘汰时需从哈希表中移除）
value int // 缓存 value
prev *Node // 前驱指针
next *Node // 后继指针
}
// LRUCache LRU 缓存核心结构
type LRUCache struct {
capacity int // 缓存容量
m map[int]*Node // 哈希表：key -> 节点
head *Node // 虚拟头节点（简化边界处理）
tail *Node // 虚拟尾节点
}
// Constructor 初始化 LRU 缓存
func Constructor(capacity int) LRUCache {
// 初始化虚拟头尾节点，互相指向
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*Node),
head: head,
tail: tail,
}
}
// addToHead 将节点添加到链表头部（标记为最近访问）
func (lc *LRUCache) addToHead(node *Node) {
node.prev = lc.head
node.next = lc.head.next
lc.head.next.prev = node
lc.head.next = node
}
// removeNode 删除指定节点
func (lc *LRUCache) removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
// moveToHead 将节点移到头部（先删除再添加）
func (lc *LRUCache) moveToHead(node *Node) {
lc.removeNode(node)
lc.addToHead(node)
}
// removeTail 删除尾部节点（淘汰最久未访问的节点）
func (lc *LRUCache) removeTail() *Node {
node := lc.tail.prev // 尾部节点是 tail.prev
lc.removeNode(node)
return node
}
// Get 查询缓存值
// 时间复杂度：O(1)
func (lc *LRUCache) Get(key int) int {
// 1. 从哈希表查找节点，不存在返回 -1
node, ok := lc.m[key]
if !ok {
return -1
}
// 2. 节点存在，移到头部（标记为最近访问）
lc.moveToHead(node)
// 3. 返回节点值
return node.value
}
// Put 插入或更新缓存
// 时间复杂度：O(1)
func (lc *LRUCache) Put(key int, value int) {
// 1. 检查 key 是否已存在
if node, ok := lc.m[key]; ok {
// 已存在：更新 value，移到头部
node.value = value
lc.moveToHead(node)
return
}
// 2. 检查容量是否超限
if len(lc.m) >= lc.capacity {
// 超限：删除尾部节点（最久未访问）
tail := lc.removeTail()
// 从哈希表中删除
delete(lc.m, tail.key)
}
// 3. 不存在：创建新节点
newNode := &Node{key: key, value: value}
// 加入哈希表
lc.m[key] = newNode
// 加入链表头部
lc.addToHead(newNode)
}
LFU 淘汰算法
LFU（Least Frequently Used，最不经常使用）是一种基于访问频率的缓存淘汰算法，核心思想是：淘汰访问次数最少的元素，优先保留高频访问的数据。
一、LFU 核心原理
1. 与 LRU 的本质区别
| 算法 | 核心依据 | 适用场景 | 缺点 |
|---|---|---|---|
| LRU（Least Recently Used） | 最近使用时间 | 访问模式稳定，近期访问的数据未来更可能被访问 | 容易被 “突发流量” 污染（如一次性扫描大量冷数据） |
| LFU（Least Frequently Used） | 访问频率 | 访问频率差异大，高频数据长期有用 | 实现复杂；对 “临时热点” 不友好（如某数据短期高频访问后不再使用） |
二、LFU 的高效数据结构设计
业界主流的 LFU 实现采用 「双哈希表 + 双向链表」 的组合，将 Get/Put 的时间复杂度优化到 O(1)：
1. 核心数据结构
| 结构 | 作用 | 说明 |
|---|---|---|
keyMap（哈希表） | 快速查找 key 对应的节点 | Key: 缓存 key，Value: 指向节点的指针 |
freqMap（哈希表） | 快速查找频率对应的双向链表 | Key: 访问频率，Value: 该频率下的双向链表（存储所有访问次数为该值的节点） |
| 双向链表 | 维护同频率下的节点顺序 | 同频率节点中，头节点是最早加入的，尾节点是最近访问的；淘汰时优先删除头节点（结合 LRU 思想，避免 “频率缓存污染”） |
minFreq（变量） | 记录当前最小频率 | 快速定位需要淘汰的链表，无需遍历查找 |
2. 节点结构体
每个节点需包含以下字段：
type Node struct {
key int // 缓存 key（删除时需从 keyMap 中移除）
value int // 缓存 value
freq int // 访问频率
prev *Node // 双向链表前驱指针
next *Node // 双向链表后继指针
}
3. 双向链表结构体
每个频率对应一个双向链表，需支持：
AddToTail(node)：将节点添加到链表尾部（最近访问的节点放后面）RemoveNode(node)：删除指定节点IsEmpty()：判断链表是否为空（为空时从 freqMap 中删除，避免内存泄漏）
type LinkedList struct {
head *Node // 虚拟头节点（简化边界处理）
tail *Node // 虚拟尾节点
size int // 链表长度
}
4. 实现
// Node 双向链表节点
type Node struct {
key, value int
freq int // 频率，等于 freqMap 中的 key
prev, next *Node
}
// LinkedList 双向链表（同频率节点的集合）
type LinkedList struct {
head *Node
tail *Node
size int
}
// NewLinkedList 初始化双向链表（带虚拟头尾节点）
func NewLinkedList() *LinkedList {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return &LinkedList{
head: head,
tail: tail,
size: 0,
}
}
// AddToTail 将节点添加到链表尾部（最近访问的节点放后面）
func (ll *LinkedList) AddToTail(node *Node) {
node.prev = ll.tail.prev
node.next = ll.tail
ll.tail.prev.next = node
ll.tail.prev = node
ll.size++
}
// RemoveNode 删除指定节点
func (ll *LinkedList) RemoveNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
node.prev = nil
node.next = nil
ll.size--
}
// IsEmpty 判断链表是否为空
func (ll *LinkedList) IsEmpty() bool {
return ll.size == 0
}
// LFUCache LFU 缓存核心结构
type LFUCache struct {
capacity int // 缓存容量
minFreq int // 当前最小频率
keyMap map[int]*Node // key - 节点
freqMap map[int]*LinkedList // 频率 - 双向链表
}
// Constructor 初始化 LFU 缓存
func Constructor(capacity int) LFUCache {
return LFUCache{
capacity: capacity,
minFreq: 0,
keyMap: make(map[int]*Node, capacity),
freqMap: make(map[int]*LinkedList),
}
}
func (lc *LFUCache) Get(key int) int {
node, ok := lc.keyMap[key]
if !ok {
return -1
}
// 更新节点访问频率
lc.updateFreq(node)
return node.value
}
func (lc *LFUCache) Put(key, value int) {
if lc.capacity == 0 {
return
}
// 1. key 存在，更新 value 并增加访问频率
if node, ok := lc.keyMap[key]; ok {
node.value = value
lc.updateFreq(node)
return
}
// 2. 容量已满，淘汰最小频率里的节点
if len(lc.keyMap) >= lc.capacity {
// 获取最小频率对应的链表
minFreqList := lc.freqMap[lc.minFreq]
// 删除链表的头节点（最早加入的节点）
deletedNode := minFreqList.head.next
minFreqList.RemoveNode(deletedNode)
// 从 keyMap 中删除
delete(lc.keyMap, deletedNode.key)
// 如果链表为空，从 freqMap 中删除
if minFreqList.IsEmpty() {
delete(lc.freqMap, lc.minFreq)
}
}
// 3. 新建节点
newNode := &Node{
key: key,
value: value,
freq: 1,
}
lc.keyMap[key] = newNode
// 加入 freqMap 中频率为1的链表（不存在则创建）
if _, ok := lc.freqMap[1]; !ok {
lc.freqMap[1] = NewLinkedList()
}
lc.freqMap[1].AddToTail(newNode)
// 更新最小频率为1
lc.minFreq = 1
}
func (lc *LFUCache) updateFreq(node *Node) {
oldFreq := node.freq
// 1、从老的双链表里删除
oldFreqList := lc.freqMap[oldFreq]
oldFreqList.RemoveNode(node)
// 如果旧链表是空的，且旧频率是当前最小频率，更新 minFreq++
if oldFreqList.IsEmpty() {
delete(lc.freqMap, oldFreq)
if oldFreq == lc.minFreq {
lc.minFreq++
}
}
// 2、加入到新的里
node.freq++
newFreq := node.freq
// 加入新频率的链表（不存在则创建）
if _, ok := lc.freqMap[newFreq]; !ok {
lc.freqMap[newFreq] = NewLinkedList()
}
lc.freqMap[newFreq].AddToTail(node)
}