【日拱一卒】鏈表——如何實現lru
LRU
Redis的記憶體淘汰機制好幾種，如ttl、random、lru。
lru（less recently used）即最近最少使用策略，表示在最近一段時間內最少被使用到的Redis鍵，如果遇到記憶體不足，會有限淘汰這部分鍵來騰出更多空間。
今天就來說說lru這種淘汰策略是如何通過鏈表這種結構實現的。
難點
在鏈表結構中，如何表示最近訪問的節點和如何表示最久沒有訪問的節點？
如何判定一個鏈表中是否存在要查找的節點？
如何向鏈表結構插入節點，並放在最近最新的節點位置？
如果在鏈表中刪除一個節點？
思路
結合上面的難點，我們可以構建一個可以解決問題的鏈表模型。
如何表示最近訪問的節點和如何表示最久沒有訪問的節點
可以設計一個雙向鏈表，頭結點表示最近訪問的節點，尾結點表示最久沒有訪問的節點。使用雙向鏈表是為了查找和定位更加方便。
如何判定一個鏈表中是否存在要查找的節點
解決這個問題，最直接的思路就是遍歷整個鏈表，依次匹配如果找到相同的值，對應的節點就是待查找的節點，如果遍歷完整個鏈表，還是沒有找到，表示該鏈表不存在該節點。
還有一種思路是將鏈表的所有節點存放到一個map結合中，查找的時候直接通過map的key進行查找即可。
如何向鏈表結構插入節點，並放在最近最新的節點位置
結合前面幾篇，我們知道，鏈表的插入和刪除是非常方便的，但是在lru問題背景下，如果插入節點並保證是最新的位置呢？顯然最新的節點是要放到頭結點的。
另外需要注意的點是，插入之前需要先查找這個節點是否存在鏈表中，如果存在需要先刪除。
如果在鏈表中刪除一個節點
刪除一個節點的前置步驟應該是先判定一個節點是否存在鏈表中，如果存在刪除即可，如果不存在則無需刪除。
通過以上幾個問題，我們大概可以構想出幾個原子函數
- 初始化雙向鏈表結構
- 查找指定節點
- 插入指定節點
- 刪除指定節點
下面我們主要看如何實現這幾個函數就可以了，主要程式碼如下
type LRUCache struct {
Cap int
Map map[int]*Node
Head *Node
Last *Node
}
type Node struct {
Val int
Key int
Pre *Node
Next *Node
}
func Constructor(capacity int) LRUCache {
cache := LRUCache{
Cap: capacity,
Map: make(map[int]*Node, capacity),
Head: &Node{},
Last: &Node{},
}
cache.Head.Next = cache.Last
cache.Last.Pre = cache.Head
return cache
}
func (this *LRUCache) Get(key int) int {
node, ok := this.Map[key]
if !ok {
return -1
}
this.remove(node)
this.setHeader(node)
return node.Val
}
func (this *LRUCache) Put(key int, value int) {
node, ok := this.Map[key]
if ok {
this.remove(node)
} else {
if len(this.Map) == this.Cap {
delete(this.Map, this.Last.Pre.Key)
this.remove(this.Last.Pre)
}
node = &Node{Val: value, Key: key}
this.Map[node.Key] = node
}
node.Val = value
this.setHeader(node)
}
func (this *LRUCache) setHeader(node *Node) {
this.Head.Next.Pre = node
node.Next = this.Head.Next
this.Head.Next = node
node.Pre = this.Head
}
func (this *LRUCache) remove(node *Node) {
node.Pre.Next = node.Next
node.Next.Pre = node.Pre
}
初始化的雙向鏈表如上圖所示，一個節點包括數據部分data，前繼節點pre和後繼節點next。
所有節點數據放入map集合中。
Get()方法會在map中查找，如果不存在，則直接返回。如果存在，則調用remove先刪除該節點，再調用setHeader將節點放入頭結點。
Put()方法會首先在map中查找對應節點，如果找到，則先調用remove刪除方法刪除改節點，並調用setHeader方法將節點放入頭結點。
至此一個lru的淘汰策略使用一個雙向鏈表就實現了。
鏈表總結
前面幾篇，分別介紹了通過鏈表結構如何實現鏈表反轉、判斷鏈表是否有環、鏈表結構的迴文判斷、有序鏈表的合併以及本篇的lru實現。
鏈表具備插入刪除方便，但是查找效率較低的特性。
以下是對於鏈表結構的梳理
如果您覺得閱讀本文對您有幫助，請點一下「推薦」按鈕，您的「推薦」將是我最大的寫作動力！如果您想持續關注我的文章，請掃描二維碼，關注JackieZheng的微信公眾號，我會將我的文章推送給您，並和您一起分享我日常閱讀過的優質文章。
