使用 Go 语言实现 LRU 缓存

在日常开发中，缓存是提高系统性能的重要手段。LRU（Least Recently Used）缓存是一种基于“最近最少使用”策略的缓存系统，其目的是在空间受限的情况下保留最新、最常用的数据。当缓存空间不足时，LRU 缓存会优先淘汰最久未被使用的数据，从而保持缓存的时效性。本文将详细讲解如何使用 Go 语言实现一个 LRU 缓存。

LRU 缓存的关键特性

• 快速访问缓存内容：Get 操作的时间复杂度为 (O(1))。
• 快速插入和更新缓存：Put 操作的时间复杂度也为 (O(1))。
• 淘汰最久未使用的数据：当缓存满时，移除最久未访问的数据。

数据结构选型

为了实现 LRU 缓存的上述特性，常用的数据结构组合为 哈希表 和 双向链表：

• 哈希表：用于快速访问缓存节点。
• 双向链表：管理节点的访问顺序。每次访问时，将节点移动到链表头部；当缓存满时，移除链表尾部节点（即最久未访问的数据）。

通过这种组合，Get 和 Put 的时间复杂度均为 (O(1))。

LRU 缓存的结构设计

在 LRU 缓存的设计中，我们需要以下两个核心组件：

1. 双向链表节点 Node：

   • 存储缓存的 key 和 value。
   • 通过 prev 和 next 指针指向前后节点。

2. LRUCache 缓存结构：

   • capacity：缓存的容量。
   • cache：使用 map[int]*Node 作为哈希表，存储键值对和链表节点的映射。
   • head 和 tail：虚拟头尾节点，用于链表的边界处理，避免在插入和删除操作时对边界条件进行额外判断。

操作流程图

下面是 LRU 缓存的整体操作流程概览：

代码实现

1. 定义节点和缓存结构

我们首先定义双向链表节点 Node 和 LRUCache 结构：

package main

import "fmt"

// 双向链表的节点
type Node struct {
	key, value int
	prev, next *Node
}

// LRUCache 缓存结构
type LRUCache struct {
	capacity   int
	cache      map[int]*Node // 哈希表，快速定位节点
	head, tail *Node         // 虚拟头尾节点
}

2. 初始化 LRU 缓存

在 Constructor 方法中，初始化缓存容量 capacity 和哈希表 cache，并创建 head 和 tail 虚拟节点。head 和 tail 之间没有数据节点，它们仅用于简化节点插入和删除的边界处理。此时，链表初始状态如下：

    head <--> tail

初始化代码如下：

// 构造函数
func Constructor(capacity int) LRUCache {
	cache := LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     &Node{},
		tail:     &Node{},
	}
	cache.head.next = cache.tail
	cache.tail.prev = cache.head
	return cache
}

3. 获取缓存值（Get 方法）

Get 方法根据 key 查找缓存中的数据。如果数据存在，则将该节点移到链表头部，标记为“最近使用”；如果数据不存在，则返回 -1。

// 获取缓存中的值
func (this *LRUCache) Get(key int) int {
	if node, found := this.cache[key]; found {
		this.moveToHead(node) // 访问后移至头部
		return node.value
	}
	return -1 // 如果不存在，返回 -1
}

在调用 moveToHead 方法时，节点被移动到链表头部。假设我们在链表中有节点顺序：head <-> A <-> B <-> tail，访问 B 后，链表状态变为：

    head <--> B <--> A <--> tail

4. 更新或插入值（Put 方法）

Put 方法根据 key 更新值，或在缓存中插入新的键值对。如果缓存超过容量限制，则移除链表尾部的节点。

// 更新或插入值
func (this *LRUCache) Put(key int, value int) {
	if node, found := this.cache[key]; found {
		node.value = value
		this.moveToHead(node) // 已存在的节点移至头部
	} else {
		// 创建新节点并加入头部
		newNode := &Node{key: key, value: value}
		this.cache[key] = newNode
		this.addNode(newNode)

		// 超出容量时，删除尾节点
		if len(this.cache) > this.capacity {
			tail := this.popTail()
			delete(this.cache, tail.key)
		}
	}
}

当缓存满时，popTail 方法删除链表尾部节点。假设链表当前状态为：head <-> B <-> A <-> tail，插入新节点 C 后，链表状态变为：

    head <--> C <--> B <--> tail

节点 A 被淘汰，从而控制了缓存的空间限制。

5. 辅助方法

addNode、removeNode、moveToHead 和 popTail 是缓存核心操作的辅助方法，用于管理链表中节点的插入、删除和移动。

// 添加节点至头部
func (this *LRUCache) addNode(node *Node) {
	node.prev = this.head
	node.next = this.head.next
	this.head.next.prev = node
	this.head.next = node
}

// 删除节点
func (this *LRUCache) removeNode(node *Node) {
	prev := node.prev
	next := node.next
	prev.next = next
	next.prev = prev
}

// 移动节点到头部
func (this *LRUCache) moveToHead(node *Node) {
	this.removeNode(node)
	this.addNode(node)
}

// 弹出尾部节点
func (this *LRUCache) popTail() *Node {
	tail := this.tail.prev
	this.removeNode(tail)
	return tail
}

插入节点到链表头部的图示

addNode 方法的核心步骤如下：假设链表初始状态为 head <-> A <-> B <-> tail，插入新节点 node 到 head 后，链表状态变为：

    head <--> node <--> A <--> B <--> tail

6. 单元测试代码

为验证实现正确性，可以使用以下测试：

import "testing"

func TestLRUCache(t *testing.T) {
	cache := Constructor(2)

	cache.Put(1, 1)
	cache.Put(2, 2)
	if cache.Get(1) != 1 {
		t.Errorf("Expected 1, got %d", cache.Get(1))
	}

	cache.Put(3, 3) // 淘汰 key 2
	if cache.Get(2) != -1 {
		t.Errorf("Expected -1, got %d", cache.Get(2))
	}

	cache.Put(4, 4) // 淘汰 key 1
	if cache.Get(1) != -1 {
		t.Errorf("Expected -1, got %d", cache.Get(1))
	}
	if cache.Get(3) != 3 {
		t.Errorf("Expected 3, got %d", cache.Get(3))
	}
	if cache.Get(4) != 4 {
		t.Errorf("Expected 4, got %d", cache.Get(4))
	}
}

总结

通过双向链表和哈希表的结合，实现了一个高效的 LRU 缓存，使 Get和 Put 操作在 O(1) 的时间内完成。双向链表和虚拟节点的设计简化了链表边界的处理，广泛适用于缓存系统中。