LRU（Least Recently Used）演算法是一種常見的快取替換策略。當快取達到預設上限時，快取會自動淘汰最近最少使用的數據，以釋放空間。
在 Golang 中，我們可以使用雙向鍊錶和雜湊表來實作 LRU 快取。在本文中，我們將介紹如何使用這兩種資料結構實作 LRU 快取。
雙向鍊錶的作用在於維護快取的資料順序，每次插入新資料或存取資料時，都會提前此資料。同時，在快取達到上限時，我們可以從鍊錶的末端刪除最近最少使用的資料。
雜湊表的作用在於加速資料的查找，每次進行資料存取時，透過雜湊表中儲存的資料索引，我們可以快速地查找到對應的快取資料。因此，我們將在實作過程中對哈希表進行操作。
接下來，我們將講解如何實作基於雙向鍊錶和雜湊表的 LRU 快取。我們定義一個 LRUCache 結構體，並宣告鍊錶頭和鍊錶尾指針，以及哈希表 map 和快取容量 capacity。
type LRUCache struct {
head, tail *entry // 链表头和链表尾指针
cache map[int]*entry // 哈希表存储缓存中的数据
capacity int // 缓存容量
}接下來，我們將定義雙向鍊錶節點的結構體。
type entry struct {
key, value int // 存储节点的键值对
prev, next *entry // 前驱和后继指针
}這裡，我們使用 prev 和 next 分別表示節點的前驅和後繼指針，key 和 value 分別表示該節點的鍵值對。
接下來，我們將定義 LRUCache 的建構子 NewLRUCache，並傳入快取容量 capacity。
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
cache: make(map[int]*entry),
capacity: capacity,
}
}在建構函式中，我們將初始化雜湊表和快取容量。
接下來，我們將定義 LRUCache 的 Get 和 Put 方法來實現資料的存取和儲存。
Get 方法的實現：
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 更新节点位置
c.moveToHead(elem)
return elem.value
}
return -1
}首先，我們從哈希表中查找是否存在相應的數據，如果存在，則將節點移到鍊錶的頭部，並返回節點存儲的值。否則，返回 -1。
下面是 moveToHead 方法的實作：
func (c *LRUCache) moveToHead(elem *entry) {
if elem == c.head {
return
} else if elem == c.tail {
c.tail = elem.prev
} else {
elem.prev.next = elem.next
elem.next.prev = elem.prev
}
elem.prev = nil
elem.next = c.head
c.head.prev = elem
c.head = elem
}此方法接收一個節點指標 elem，用於將該節點移到鍊錶頭部。首先，如果該節點已經是鍊錶頭部，則返回；否則，如果該節點是鍊錶尾部，則更新鍊錶尾部指標 tail；否則，將該節點從鍊錶中刪除，並將該節點放置到鍊錶頭部。
Put 方法的實作：
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
elem.value = value
c.moveToHead(elem)
} else {
// 创建新节点
elem := &entry{key: key, value: value}
c.cache[key] = elem
if c.head == nil {
c.head = elem
c.tail = elem
} else {
// 在链表头部插入新节点
elem.next = c.head
c.head.prev = elem
c.head = elem
}
// 判断缓存是否达到预设上限
if len(c.cache) > c.capacity {
// 删除链表尾部节点和哈希表中的数据
delete(c.cache, c.tail.key)
c.tail = c.tail.prev
c.tail.next = nil
}
}
}首先，我們從雜湊表中尋找是否存在對應的數據，如果存在，則更新節點儲存的值，並呼叫moveToHead 方法將該節點移到鍊錶的頭部。否則，建立一個新的節點，並將該節點插入到鍊錶的頭部。如果快取達到預設上限，則刪除鍊錶的尾部節點和雜湊表中的資料。
最後，我們將完整的程式碼整合到一起：
type LRUCache struct {
head, tail *entry
cache map[int]*entry
capacity int
}
type entry struct {
key, value int
prev, next *entry
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
cache: make(map[int]*entry),
capacity: capacity,
}
}
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 更新节点位置
c.moveToHead(elem)
return elem.value
}
return -1
}
func (c *LRUCache) moveToHead(elem *entry) {
if elem == c.head {
return
} else if elem == c.tail {
c.tail = elem.prev
} else {
elem.prev.next = elem.next
elem.next.prev = elem.prev
}
elem.prev = nil
elem.next = c.head
c.head.prev = elem
c.head = elem
}
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
elem.value = value
c.moveToHead(elem)
} else {
// 创建新节点
elem := &entry{key: key, value: value}
c.cache[key] = elem
if c.head == nil {
c.head = elem
c.tail = elem
} else {
// 在链表头部插入新节点
elem.next = c.head
c.head.prev = elem
c.head = elem
}
// 判断缓存是否达到预设上限
if len(c.cache) > c.capacity {
// 删除链表尾部节点和哈希表中的数据
delete(c.cache, c.tail.key)
c.tail = c.tail.prev
c.tail.next = nil
}
}
}在本文中，我們已經介紹瞭如何使用雙向鍊錶和雜湊表來實作 LRU 快取演算法。透過這種演算法的實現，我們可以有效地管理緩存，優化資料的存取效率。
以上是golang lru實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
