LRU 与 LFU 缓存淘汰算法详解
LRU (Least Recently Used)
核心思路
LRU 的核心思想很直观：如果数据最近被访问过，那么将来它被访问的概率也更高；反之，很久没被访问的，就更可能被淘汰。这是一种基于时间局部性的策略。
实现上，LRU 是哈希表（提供 O(1) 查找）和双向链表（提供 O(1) 顺序维护）的完美结合。哈希表存 key 到节点的映射，双向链表维护访问顺序。
为什么用双向链表？单链表虽然能 O(1) 插入头部、删除尾部，但若要删除中间节点（比如访问命中时），需要遍历找到前驱节点，复杂度变成 O(n)。双向链表可以直接通过节点指针访问 prev 和 next，保证所有操作都是 O(1)。
读写流程
读取数据： 当客户端请求获取某个 key 的数据时：
- 先在哈希表中查找 key。若不存在，返回 null。
- 若存在，拿到对应的链表节点。
- 关键步骤：将该节点从当前位置移除，并重新插入到链表头部。因为刚刚被访问，它变成了'最新'的项。
- 返回 value。
这样每次访问都会把数据提升到'排行榜'第一名，保护它不被轻易淘汰。
写入数据： 当客户端要求插入或更新键值对时：
- 检查 key 是否已存在。
- 存在：更新 value，并将节点移动到链表头部。
- 不存在：
- 检查容量。如果已满，淘汰链表尾部的节点（最久未使用），并在哈希表中删除该 key。
- 创建新节点，插入链表头部，并加入哈希表。
Go 语言实现
下面是完整的 Go 实现，使用了哨兵节点（dummy head/tail）来简化边界处理。
package main
import "fmt"
// Node 双向链表节点
type Node struct {
key, value int
prev, next *Node
}
// LRUCache 结构
type LRUCache struct {
capacity int
cache map[int]*Node
head *Node // dummy head
tail *Node // dummy tail
}
// Constructor 初始化
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make([]*Node),
head: head,
tail: tail,
}
}
Get(key ) {
node, ok := l.cache[key]; ok {
l.moveToHead(node)
node.value
}
}
Put(key , value ) {
node, ok := l.cache[key]; ok {
node.value = value
l.moveToHead(node)
}
(l.cache) >= l.capacity {
removed := l.removeTail()
(l.cache, removed.key)
}
newNode := &Node{key: key, value: value}
l.cache[key] = newNode
l.addToHead(newNode)
}
addToHead(node *Node) {
node.prev = l.head
node.next = l.head.next
l.head.next.prev = node
l.head.next = node
}
removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
moveToHead(node *Node) {
l.removeNode(node)
l.addToHead(node)
}
removeTail() *Node {
node := l.tail.prev
l.removeNode(node)
node
}
{
lru := Constructor()
lru.Put(, )
lru.Put(, )
fmt.Println(lru.Get())
lru.Put(, )
fmt.Println(lru.Get())
lru.Put(, )
fmt.Println(lru.Get())
fmt.Println(lru.Get())
fmt.Println(lru.Get())
}
