使用Go語言實現(xiàn)LRU緩存的代碼詳解

更新時間：2024年11月01日 09:43:37 作者：tatasix

在日常開發(fā)中,緩存是提高系統(tǒng)性能的重要手段,LRU緩存是一種基于“最近最少使用”策略的緩存系統(tǒng),其目的是在空間受限的情況下保留最新、最常用的數(shù)據(jù),本文將詳細講解如何使用?Go?語言實現(xiàn)一個?LRU?緩存,需要的朋友可以參考下

引言

在日常開發(fā)中，緩存是提高系統(tǒng)性能的重要手段。LRU（Least Recently Used）緩存是一種基于“最近最少使用”策略的緩存系統(tǒng)，其目的是在空間受限的情況下保留最新、最常用的數(shù)據(jù)。當緩存空間不足時，LRU 緩存會優(yōu)先淘汰最久未被使用的數(shù)據(jù)，從而保持緩存的時效性。本文將詳細講解如何使用 Go 語言實現(xiàn)一個 LRU 緩存。

LRU 緩存的關鍵特性

快速訪問緩存內(nèi)容：Get 操作的時間復雜度為 (O(1))。
快速插入和更新緩存：Put 操作的時間復雜度也為 (O(1))。
淘汰最久未使用的數(shù)據(jù)：當緩存滿時，移除最久未訪問的數(shù)據(jù)。

數(shù)據(jù)結構選型

為了實現(xiàn) LRU 緩存的上述特性，常用的數(shù)據(jù)結構組合為 哈希表 和 雙向鏈表：

哈希表：用于快速訪問緩存節(jié)點。
雙向鏈表：管理節(jié)點的訪問順序。每次訪問時，將節(jié)點移動到鏈表頭部；當緩存滿時，移除鏈表尾部節(jié)點（即最久未訪問的數(shù)據(jù)）。

通過這種組合，Get 和 Put 的時間復雜度均為 (O(1))。

LRU 緩存的結構設計

在 LRU 緩存的設計中，我們需要以下兩個核心組件：

雙向鏈表節(jié)點 Node：
- 存儲緩存的 key 和 value。
- 通過 prev 和 next 指針指向前后節(jié)點。
LRUCache 緩存結構：
- capacity：緩存的容量。
- cache：使用 map[int]*Node 作為哈希表，存儲鍵值對和鏈表節(jié)點的映射。
- head 和 tail：虛擬頭尾節(jié)點，用于鏈表的邊界處理，避免在插入和刪除操作時對邊界條件進行額外判斷。

操作流程圖

下面是 LRU 緩存的整體操作流程概覽：

代碼實現(xiàn)

1. 定義節(jié)點和緩存結構

我們首先定義雙向鏈表節(jié)點 Node 和 LRUCache 結構：

package main

import "fmt"

// 雙向鏈表的節(jié)點
type Node struct {
	key, value int
	prev, next *Node
}

// LRUCache 緩存結構
type LRUCache struct {
	capacity   int
	cache      map[int]*Node // 哈希表，快速定位節(jié)點
	head, tail *Node         // 虛擬頭尾節(jié)點
}

2. 初始化 LRU 緩存

在 Constructor 方法中，初始化緩存容量 capacity 和哈希表 cache，并創(chuàng)建 head 和 tail 虛擬節(jié)點。head 和 tail 之間沒有數(shù)據(jù)節(jié)點，它們僅用于簡化節(jié)點插入和刪除的邊界處理。此時，鏈表初始狀態(tài)如下：

    head <--> tail

初始化代碼如下：

// 構造函數(shù)
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 方法根據(jù) key 查找緩存中的數(shù)據(jù)。如果數(shù)據(jù)存在，則將該節(jié)點移到鏈表頭部，標記為“最近使用”；如果數(shù)據(jù)不存在，則返回 -1。

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

在調(diào)用 moveToHead 方法時，節(jié)點被移動到鏈表頭部。假設我們在鏈表中有節(jié)點順序：head <-> A <-> B <-> tail，訪問 B 后，鏈表狀態(tài)變?yōu)椋?/p>

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

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

Put 方法根據(jù) key 更新值，或在緩存中插入新的鍵值對。如果緩存超過容量限制，則移除鏈表尾部的節(jié)點。

// 更新或插入值
func (this *LRUCache) Put(key int, value int) {
	if node, found := this.cache[key]; found {
		node.value = value
		this.moveToHead(node) // 已存在的節(jié)點移至頭部
	} else {
		// 創(chuàng)建新節(jié)點并加入頭部
		newNode := &Node{key: key, value: value}
		this.cache[key] = newNode
		this.addNode(newNode)

		// 超出容量時，刪除尾節(jié)點
		if len(this.cache) > this.capacity {
			tail := this.popTail()
			delete(this.cache, tail.key)
		}
	}
}

當緩存滿時，popTail 方法刪除鏈表尾部節(jié)點。假設鏈表當前狀態(tài)為：head <-> B <-> A <-> tail，插入新節(jié)點 C 后，鏈表狀態(tài)變?yōu)椋?/p>

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

節(jié)點 A 被淘汰，從而控制了緩存的空間限制。

5. 輔助方法

addNode、removeNode、moveToHead 和 popTail 是緩存核心操作的輔助方法，用于管理鏈表中節(jié)點的插入、刪除和移動。

// 添加節(jié)點至頭部
func (this *LRUCache) addNode(node *Node) {
	node.prev = this.head
	node.next = this.head.next
	this.head.next.prev = node
	this.head.next = node
}

// 刪除節(jié)點
func (this *LRUCache) removeNode(node *Node) {
	prev := node.prev
	next := node.next
	prev.next = next
	next.prev = prev
}

// 移動節(jié)點到頭部
func (this *LRUCache) moveToHead(node *Node) {
	this.removeNode(node)
	this.addNode(node)
}

// 彈出尾部節(jié)點
func (this *LRUCache) popTail() *Node {
	tail := this.tail.prev
	this.removeNode(tail)
	return tail
}

插入節(jié)點到鏈表頭部的圖示

addNode 方法的核心步驟如下：假設鏈表初始狀態(tài)為 head <-> A <-> B <-> tail，插入新節(jié)點 node 到 head 后，鏈表狀態(tài)變?yōu)椋?/p>

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

6. 單元測試代碼

為驗證實現(xiàn)正確性，可以使用以下測試：

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))
	}
}