Go语言实现LRU缓存（深入浅出讲解数据结构与缓存淘汰算法）

什么是 LRU 缓存？

LRU 的核心思想是：如果一个数据最近被访问过，那么它在未来被再次访问的概率也更高。因此，当缓存容量达到上限时，优先淘汰“最久未被使用”的数据。

举个生活中的例子：你书桌上只能放 3 本书。当你需要看第 4 本时，你会把最近最少翻阅的那本收进书柜。这就是 LRU 的朴素逻辑。

LRU 的数据结构设计

要高效实现 LRU，我们需要两个关键数据结构：

• 哈希表（map）：用于 O(1) 时间复杂度的快速查找。
• 双向链表：用于维护元素的访问顺序，链表头部是最近使用的，尾部是最久未使用的。

每次访问一个 key 时，我们将其对应的节点移到链表头部；插入新元素时，也放在头部；当容量满时，删除尾部节点并从 map 中移除。

Go 语言实现 LRU 缓存

下面是一个完整的、带并发安全的 LRU 缓存实现：

package mainimport (	"container/list"	"sync")// Entry 表示缓存中的一个条目type Entry struct {	Key   interface{}	Value interface{}}// LRUCache 是线程安全的 LRU 缓存结构type LRUCache struct {	capacity int	cache    map[interface{}]*list.Element // 哈希表，用于快速查找	ll       *list.List                    // 双向链表，维护访问顺序	mu       sync.RWMutex                  // 读写锁，保证并发安全}// NewLRUCache 创建一个新的 LRU 缓存func NewLRUCache(capacity int) *LRUCache {	return &LRUCache{		capacity: capacity,		cache:    make(map[interface{}]*list.Element),		ll:       list.New(),	}}// Get 获取缓存中的值func (c *LRUCache) Get(key interface{}) (value interface{}, ok bool) {	c.mu.Lock()	defer c.mu.Unlock()	if ele, hit := c.cache[key]; hit {		c.ll.MoveToFront(ele) // 移动到头部，表示最近使用		return ele.Value.(*Entry).Value, true	}	return}// Put 添加或更新缓存func (c *LRUCache) Put(key, value interface{}) {	c.mu.Lock()	defer c.mu.Unlock()	if ele, ok := c.cache[key]; ok {		// 更新已有 key		c.ll.MoveToFront(ele)		ele.Value = &Entry{key, value}	} else {		// 新增 key		ele := c.ll.PushFront(&Entry{key, value})		c.cache[key] = ele		// 如果超出容量，删除尾部元素		if c.ll.Len() > c.capacity {			tail := c.ll.Back()			if tail != nil {				c.ll.Remove(tail)				delete(c.cache, tail.Value.(*Entry).Key)			}		}	}}// Len 返回当前缓存大小func (c *LRUCache) Len() int {	c.mu.RLock()	defer c.mu.RUnlock()	return c.ll.Len()}

使用示例

下面是如何使用我们刚实现的 LRU 缓存：

func main() {	cache := NewLRUCache(2) // 容量为2	cache.Put("a", 1)	cache.Put("b", 2)	fmt.Println(cache.Get("a")) // 输出: 1 true	cache.Put("c", 3) // 此时 "b" 被淘汰	_, ok := cache.Get("b")	fmt.Println(ok) // 输出: false	fmt.Println(cache.Len()) // 输出: 2}

为什么选择 Go 语言实现 LRU？

Go 语言以其简洁的语法、强大的标准库（如 container/list）和内置并发支持（goroutine + channel / sync 包），非常适合实现高性能的数据结构。同时，Go 在微服务、中间件、数据库等领域广泛应用，掌握 Go语言 LRU缓存 实现对提升系统性能至关重要。

总结

通过本文，你已经学会了：

• LRU 缓存淘汰算法的核心思想
• 如何结合哈希表与双向链表实现高效 LRU
• 用 Go 语言编写线程安全的 LRU 缓存
• 实际应用场景与性能优势

掌握 数据结构 和 缓存淘汰算法 是成为优秀 Go 工程师的重要一步。希望这篇教程能为你打下坚实基础！

—— 用 Go 构建高性能系统，从理解 LRU 开始 ——