LRU

Redis的內(nèi)存淘汰機(jī)制好幾種，如ttl、random、lru。

lru（less recently used）即最近最少使用策略，表示在最近一段時(shí)間內(nèi)最少被使用到的Redis鍵，如果遇到內(nèi)存不足，會(huì)有限淘汰這部分鍵來騰出更多空間。

今天就來說說lru這種淘汰策略是如何通過鏈表這種結(jié)構(gòu)實(shí)現(xiàn)的。

難點(diǎn)

在鏈表結(jié)構(gòu)中，如何表示最近訪問的節(jié)點(diǎn)和如何表示最久沒有訪問的節(jié)點(diǎn)？

如何判定一個(gè)鏈表中是否存在要查找的節(jié)點(diǎn)？

如何向鏈表結(jié)構(gòu)插入節(jié)點(diǎn)，并放在最近最新的節(jié)點(diǎn)位置？

如果在鏈表中刪除一個(gè)節(jié)點(diǎn)？

思路

結(jié)合上面的難點(diǎn)，我們可以構(gòu)建一個(gè)可以解決問題的鏈表模型。

如何表示最近訪問的節(jié)點(diǎn)和如何表示最久沒有訪問的節(jié)點(diǎn)

可以設(shè)計(jì)一個(gè)雙向鏈表，頭結(jié)點(diǎn)表示最近訪問的節(jié)點(diǎn)，尾結(jié)點(diǎn)表示最久沒有訪問的節(jié)點(diǎn)。使用雙向鏈表是為了查找和定位更加方便。

如何判定一個(gè)鏈表中是否存在要查找的節(jié)點(diǎn)

解決這個(gè)問題，最直接的思路就是遍歷整個(gè)鏈表，依次匹配如果找到相同的值，對(duì)應(yīng)的節(jié)點(diǎn)就是待查找的節(jié)點(diǎn)，如果遍歷完整個(gè)鏈表，還是沒有找到，表示該鏈表不存在該節(jié)點(diǎn)。

還有一種思路是將鏈表的所有節(jié)點(diǎn)存放到一個(gè)map結(jié)合中，查找的時(shí)候直接通過map的key進(jìn)行查找即可。

如何向鏈表結(jié)構(gòu)插入節(jié)點(diǎn)，并放在最近最新的節(jié)點(diǎn)位置

結(jié)合前面幾篇，我們知道，鏈表的插入和刪除是非常方便的，但是在lru問題背景下，如果插入節(jié)點(diǎn)并保證是最新的位置呢？顯然最新的節(jié)點(diǎn)是要放到頭結(jié)點(diǎn)的。

另外需要注意的點(diǎn)是，插入之前需要先查找這個(gè)節(jié)點(diǎn)是否存在鏈表中，如果存在需要先刪除。

如果在鏈表中刪除一個(gè)節(jié)點(diǎn)

刪除一個(gè)節(jié)點(diǎn)的前置步驟應(yīng)該是先判定一個(gè)節(jié)點(diǎn)是否存在鏈表中，如果存在刪除即可，如果不存在則無需刪除。

通過以上幾個(gè)問題，我們大概可以構(gòu)想出幾個(gè)原子函數(shù)

• 初始化雙向鏈表結(jié)構(gòu)
• 查找指定節(jié)點(diǎn)
• 插入指定節(jié)點(diǎn)
• 刪除指定節(jié)點(diǎn)

下面我們主要看如何實(shí)現(xiàn)這幾個(gè)函數(shù)就可以了，主要代碼如下

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
}

初始化的雙向鏈表如上圖所示，一個(gè)節(jié)點(diǎn)包括數(shù)據(jù)部分data，前繼節(jié)點(diǎn)pre和后繼節(jié)點(diǎn)next。

所有節(jié)點(diǎn)數(shù)據(jù)放入map集合中。

Get()方法會(huì)在map中查找，如果不存在，則直接返回。如果存在，則調(diào)用remove先刪除該節(jié)點(diǎn)，再調(diào)用setHeader將節(jié)點(diǎn)放入頭結(jié)點(diǎn)。

Put()方法會(huì)首先在map中查找對(duì)應(yīng)節(jié)點(diǎn)，如果找到，則先調(diào)用remove刪除方法刪除改節(jié)點(diǎn)，并調(diào)用setHeader方法將節(jié)點(diǎn)放入頭結(jié)點(diǎn)。

至此一個(gè)lru的淘汰策略使用一個(gè)雙向鏈表就實(shí)現(xiàn)了。

鏈表總結(jié)

前面幾篇，分別介紹了通過鏈表結(jié)構(gòu)如何實(shí)現(xiàn)鏈表反轉(zhuǎn)、判斷鏈表是否有環(huán)、鏈表結(jié)構(gòu)的回文判斷、有序鏈表的合并以及本篇的lru實(shí)現(xiàn)。

鏈表具備插入刪除方便，但是查找效率較低的特性。

以下是對(duì)于鏈表結(jié)構(gòu)的梳理