在高性能服务开发中，缓存是提升访问速度和减少后端负载的重要手段。常见的缓存淘汰策略中，**LRU（Least Recently Used，最近最少使用）**是应用最广的一种。本篇我们用Go语言手写一个LRU缓存机制的模拟实现。
一、LRU缓存机制简介
1. 定义
LRU缓存是一种固定容量的缓存结构。当缓存已满时，它会淘汰最近最少使用的那个数据。简单理解：
谁最久没被访问，就先删除谁。
2. 使用场景
- • Web浏览器缓存
- • 数据库查询结果缓存
- • 操作系统页面置换
二、设计要求
LRU缓存应支持以下操作：
- 1.
Get(key)：如果key存在，返回对应的value，并将该key标记为最近使用；否则返回-1。 - 2.
Put(key, value)：插入或更新key。如果容量已满，需要删除最近最少使用的key。
要求两种操作都能在 O(1) 时间复杂度内完成。
三、核心数据结构
要实现 O(1) 操作，需要组合以下两种结构：
1. 哈希表（map）
- • 用于存储
key → 节点的映射； - • 可在 O(1) 时间内找到节点。
2. 双向链表
- • 用于维护数据访问的顺序；
- • 头部表示最近使用，尾部表示最久未使用；
- • 插入、删除节点都是 O(1)。
四、Go语言实现
1. 节点结构
type Node struct { key, value int prev, next *Node }
2. LRU缓存结构
type LRUCache struct { capacity int cache map[int]*Node head *Node tail *Node }
- •
head和tail是哨兵节点（dummy），方便操作。
3. 初始化
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, } }
4. 辅助方法
// moveToHead：将节点移动到头部 func (l *LRUCache) moveToHead(node *Node) { l.removeNode(node) l.addToHead(node) } // removeNode：删除链表中的节点 func (l *LRUCache) removeNode(node *Node) { prev := node.prev next := node.next prev.next = next next.prev = prev } // addToHead：在头部插入节点 func (l *LRUCache) addToHead(node *Node) { node.prev = l.head node.next = l.head.next l.head.next.prev = node l.head.next = node } // removeTail：删除尾部节点并返回它 func (l *LRUCache) removeTail() *Node { node := l.tail.prev l.removeNode(node) return node }
5. 核心操作
Get
func (l *LRUCache) Get(key int) int { if node, ok := l.cache[key]; ok { l.moveToHead(node) return node.value } return -1 }
Put
func (l *LRUCache) Put(key int, value int) { if node, ok := l.cache[key]; ok { node.value = value l.moveToHead(node) } else { newNode := &Node{key: key, value: value} l.cache[key] = newNode l.addToHead(newNode) if len(l.cache) > l.capacity { tail := l.removeTail() delete(l.cache, tail.key) } } }
五、完整代码示例
package main import "fmt" type Node struct { key, value int prev, next *Node } type LRUCache struct { capacity int cache map[int]*Node head *Node tail *Node } 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, } } func (l *LRUCache) Get(key int) int { if node, ok := l.cache[key]; ok { l.moveToHead(node) return node.value } return -1 } func (l *LRUCache) Put(key int, value int) { if node, ok := l.cache[key]; ok { node.value = value l.moveToHead(node) } else { newNode := &Node{key: key, value: value} l.cache[key] = newNode l.addToHead(newNode) if len(l.cache) > l.capacity { tail := l.removeTail() delete(l.cache, tail.key) } } } func (l *LRUCache) moveToHead(node *Node) { l.removeNode(node) l.addToHead(node) } func (l *LRUCache) removeNode(node *Node) { prev := node.prev next := node.next prev.next = next next.prev = prev } func (l *LRUCache) addToHead(node *Node) { node.prev = l.head node.next = l.head.next l.head.next.prev = node l.head.next = node } func (l *LRUCache) removeTail() *Node { node := l.tail.prev l.removeNode(node) return node } func main() { cache := Constructor(2) cache.Put(1, 1) cache.Put(2, 2) fmt.Println(cache.Get(1)) // 1 cache.Put(3, 3) // 淘汰 key=2 fmt.Println(cache.Get(2)) // -1 cache.Put(4, 4) // 淘汰 key=1 fmt.Println(cache.Get(1)) // -1 fmt.Println(cache.Get(3)) // 3 fmt.Println(cache.Get(4)) // 4 }
六、复杂度分析
- • 时间复杂度：O(1)，Get 和 Put 都只涉及哈希表查找和链表操作。
- • 空间复杂度：O(capacity)，存储固定大小的map和链表节点。
七、工程实践与优化
- 1. 线程安全
在多协程环境中，需使用sync.Mutex或sync.RWMutex保证安全。 - 2. 泛型支持（Go1.18+）
可以用泛型实现支持任意类型的key/value。 - 3. 监控统计
可增加命中率统计、淘汰计数。
八、应用场景
- • 数据库缓存：Redis内部就支持LRU策略；
- • 浏览器缓存：网页资源加载优化；
- • API限速器：存储用户最近访问记录。
九、总结
- • LRU缓存结合了 哈希表 + 双向链表；
- • 关键是 O(1) 时间内完成访问和淘汰；
- • 该思想可扩展到 LFU、ARC 等高级缓存策略。
