在高性能服务开发中，缓存是提升访问速度和减少后端负载的重要手段。常见的缓存淘汰策略中，**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 intprev, next *Node
}

2. LRU缓存结构

type LRUCache struct {capacity intcache    map[int]*Nodehead     *Nodetail     *Node
}

• head 和 tail 是哨兵节点（dummy），方便操作。

3. 初始化

func Constructor(capacity int) LRUCache {head := &Node{}tail := &Node{}head.next = tailtail.prev = headreturn 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.prevnext := node.nextprev.next = nextnext.prev = prev
}// addToHead：在头部插入节点
func (l *LRUCache) addToHead(node *Node) {node.prev = l.headnode.next = l.head.nextl.head.next.prev = nodel.head.next = node
}// removeTail：删除尾部节点并返回它
func (l *LRUCache) removeTail() *Node {node := l.tail.prevl.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 = valuel.moveToHead(node)} else {newNode := &Node{key: key, value: value}l.cache[key] = newNodel.addToHead(newNode)if len(l.cache) > l.capacity {tail := l.removeTail()delete(l.cache, tail.key)}}
}

五、完整代码示例

package mainimport "fmt"type Node struct {key, value intprev, next *Node
}type LRUCache struct {capacity intcache    map[int]*Nodehead     *Nodetail     *Node
}func Constructor(capacity int) LRUCache {head := &Node{}tail := &Node{}head.next = tailtail.prev = headreturn 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 = valuel.moveToHead(node)} else {newNode := &Node{key: key, value: value}l.cache[key] = newNodel.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.prevnext := node.nextprev.next = nextnext.prev = prev
}func (l *LRUCache) addToHead(node *Node) {node.prev = l.headnode.next = l.head.nextl.head.next.prev = nodel.head.next = node
}func (l *LRUCache) removeTail() *Node {node := l.tail.prevl.removeNode(node)return node
}func main() {cache := Constructor(2)cache.Put(1, 1)cache.Put(2, 2)fmt.Println(cache.Get(1)) // 1cache.Put(3, 3)           // 淘汰 key=2fmt.Println(cache.Get(2)) // -1cache.Put(4, 4)           // 淘汰 key=1fmt.Println(cache.Get(1)) // -1fmt.Println(cache.Get(3)) // 3fmt.Println(cache.Get(4)) // 4
}