今天為大家分享很出名的LRU算法，第一講共包括4節。
- LRU概述
- LRU使用
- LRU實作
- Redis近LRU概述
第一部分：LRU概述
LRU是Least Recently Used的縮寫，譯為最近最少使用。它的理論基礎為“最近使用的資料會在未來一段時期内仍然被使用，已經很久沒有使用的資料大機率在未來很長一段時間仍然不會被使用”由于該思想非常契合業務場景 ，并且可以解決很多實際開發中的問題，是以我們經常通過LRU的思想來作緩存，一般也将其稱為LRU緩存機制。因為恰好leetcode上有這道題，是以我幹脆把題目貼這裡。但是對于LRU而言，希望大家不要局限于本題（大家不用擔心學不會，我希望能做一個全網最簡單的版本，希望可以堅持看下去！）下面，我們一起學習一下。
題目：運用你所掌握的資料結構，設計和實作一個 LRU (最近最少使用) 緩存機制。它應該支援以下操作：擷取資料 get 和 寫入資料 put 。
擷取資料 get(key) - 如果密鑰 (key) 存在于緩存中，則擷取密鑰的值（總是正數），否則傳回 -1。
寫入資料 put(key, value) - 如果密鑰不存在，則寫入其資料值。當緩存容量達到上限時，它應該在寫入新資料之前删除最近最少使用的資料值，進而為新的資料值留出空間。
進階:你是否可以在 O(1) 時間複雜度内完成這兩種操作？
示例:
LRUCache cache = new LRUCache( 2 / 緩存容量 / );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 傳回 1
cache.put(3, 3); // 該操作會使得密鑰 2 廢棄
cache.get(2); // 傳回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 廢棄
cache.get(1); // 傳回 -1 (未找到)
cache.get(3); // 傳回 3
cache.get(4); // 傳回 4
第二部分：LRU使用
首先說一下LRUCache的示例解釋一下。
- 第一步：我們申明一個LRUCache，長度為2
幹貨|漫畫算法：LRU從實作到應用層層剖析（第一講） - 第二步：我們分别向cache裡邊put(1,1)和put(2,2)，這裡因為最近使用的是2（put也算作使用）是以2在前，1在後。
- 第三步：我們get(1)，也就是我們使用了1，是以需要将1移到前面。
- 第四步：此時我們put(3,3)，因為2是最近最少使用的，是以我們需要将2進行廢棄。此時我們再get(2)，就會傳回-1。
- 第五步：我們繼續put(4,4)，同理我們将1廢棄。此時如果get(1)，也是傳回-1。
- 第六步：此時我們get(3)，實際為調整3的位置。
- 第七步：同理，get(4)，繼續調整4的位置。
第三部分：LRU 實作（層層剖析）
通過上面的分析大家應該都能了解LRU的使用了。現在我們聊一下實作。LRU一般來講，我們是使用雙向連結清單實作。這裡我要強調的是，其實在項目中，并不絕對是這樣。比如Redis源碼裡，LRU的淘汰政策，就沒有使用雙向連結清單，而是使用一種模拟連結清單的方式。因為Redis大多是當記憶體在用（我知道可以持久化），如果再在記憶體中去維護一個連結清單，就平添了一些複雜性，同時也會多耗掉一些記憶體，後面我會單獨拉出來Redis的源碼給大家分析，這裡不細說。
回到題目，為什麼我們要選擇雙向連結清單來實作呢？看看上面的使用步驟圖，大家會發現，在整個LRUCache的使用中，我們需要頻繁的去調整首尾元素的位置。而雙向連結清單的結構，剛好滿足這一點（再啰嗦一下，前幾天我剛好看了groupcache的源碼，裡邊就是用雙向連結清單來做的LRU，當然它裡邊做了一些改進。groupcache是memcache作者實作的go版本，如果有go的讀者，可以去看看源碼，還是有一些收獲。）
下面，我們采用hashmap+雙向連結清單的方式進行實作。
首先，我們定義一個LinkNode，用以存儲元素。因為是雙向連結清單，自然我們要定義pre和next。同時，我們需要存儲下元素的key和value。val大家應該都能了解，關鍵是為什麼需要存儲key？舉個例子，比如當整個cache的元素滿了，此時我們需要删除map中的資料，需要通過LinkNode中的key來進行查詢，否則無法擷取到key。
type LRUCache struct {
m map[int]*LinkNode
cap int
head, tail *LinkNode
} 現在有了LinkNode，自然需要一個Cache來存儲所有的Node。我們定義cap為cache的長度，m用來存儲元素。head和tail作為Cache的首尾。
type LRUCache struct {
m map[int]*LinkNode
cap int
head, tail *LinkNode
} 接下來我們對整個Cache進行初始化。在初始化head和tail的時候将它們連接配接在一起。
func Constructor(capacity int) LRUCache {
head := &LinkNode{0, 0, nil, nil}
tail := &LinkNode{0, 0, nil, nil}
head.next = tail
tail.pre = head
return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
} 大概是這樣：
現在我們已經完成了Cache的構造，剩下的就是添加它的API了。因為Get比較簡單，我們先完成Get方法。這裡分兩種情況考慮，如果沒有找到元素，我們傳回-1。如果元素存在，我們需要把這個元素移動到首位置上去。
func (this *LRUCache) Get(key int) int {
head := this.head
cache := this.m
if v, exist := cache[key]; exist {
v.pre.next = v.next
v.next.pre = v.pre
v.next = head.next
head.next.pre = v
v.pre = head
head.next = v
return v.val
} else {
return -1
}
} 大概就是下面這個樣子（假若2是我們get的元素）
我們很容易想到這個方法後面還會用到，是以将其抽出。
func (this *LRUCache) moveToHead(node *LinkNode){
head := this.head
//從目前位置删除
node.pre.next = node.next
node.next.pre = node.pre
//移動到首位置
node.next = head.next
head.next.pre = node
node.pre = head
head.next = node
}
func (this *LRUCache) Get(key int) int {
cache := this.m
if v, exist := cache[key]; exist {
this.moveToHead(v)
return v.val
} else {
return -1
}
} 現在我們開始完成Put。實作Put時，有兩種情況需要考慮。假若元素存在，其實相當于做一個Get操作，也是移動到最前面（但是需要注意的是，這裡多了一個更新值的步驟）。
func (this *LRUCache) Put(key int, value int) {
head := this.head
tail := this.tail
cache := this.m
//假若元素存在
if v, exist := cache[key]; exist {
//1.更新值
v.val = value
//2.移動到最前
this.moveToHead(v)
} else {
//TODO
}
} 假若元素不存在，我們将其插入到元素首，并把該元素值放入到map中。
func (this *LRUCache) Put(key int, value int) {
head := this.head
tail := this.tail
cache := this.m
//存在
if v, exist := cache[key]; exist {
//1.更新值
v.val = value
//2.移動到最前
this.moveToHead(v)
} else {
v := &LinkNode{key, value, nil, nil}
v.next = head.next
v.pre = head
head.next.pre = v
head.next = v
cache[key] = v
}
} 但是我們漏掉了一種情況，如果恰好此時Cache中元素滿了，需要删掉最後的元素。處理完畢，附上Put函數完整代碼。
func (this *LRUCache) Put(key int, value int) {
head := this.head
tail := this.tail
cache := this.m
//存在
if v, exist := cache[key]; exist {
//1.更新值
v.val = value
//2.移動到最前
this.moveToHead(v)
} else {
v := &LinkNode{key, value, nil, nil}
if len(cache) == this.cap {
//删除最後元素
delete(cache, tail.pre.key)
tail.pre.pre.next = tail
tail.pre = tail.pre.pre
}
v.next = head.next
v.pre = head
head.next.pre = v
head.next = v
cache[key] = v
}
} 最後，我們完成所有代碼：
type LinkNode struct {
key, val int
pre, next *LinkNode
}
type LRUCache struct {
m map[int]*LinkNode
cap int
head, tail *LinkNode
}
func Constructor(capacity int) LRUCache {
head := &LinkNode{0, 0, nil, nil}
tail := &LinkNode{0, 0, nil, nil}
head.next = tail
tail.pre = head
return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
}
func (this *LRUCache) Get(key int) int {
cache := this.m
if v, exist := cache[key]; exist {
this.moveToHead(v)
return v.val
} else {
return -1
}
}
func (this *LRUCache) moveToHead(node *LinkNode) {
head := this.head
//從目前位置删除
node.pre.next = node.next
node.next.pre = node.pre
//移動到首位置
node.next = head.next
head.next.pre = node
node.pre = head
head.next = node
}
func (this *LRUCache) Put(key int, value int) {
head := this.head
tail := this.tail
cache := this.m
//存在
if v, exist := cache[key]; exist {
//1.更新值
v.val = value
//2.移動到最前
this.moveToHead(v)
} else {
v := &LinkNode{key, value, nil, nil}
if len(cache) == this.cap {
//删除末尾元素
delete(cache, tail.pre.key)
tail.pre.pre.next = tail
tail.pre = tail.pre.pre
}
v.next = head.next
v.pre = head
head.next.pre = v
head.next = v
cache[key] = v
}
} 優化後：
type LinkNode struct {
key, val int
pre, next *LinkNode
}
type LRUCache struct {
m map[int]*LinkNode
cap int
head, tail *LinkNode
}
func Constructor(capacity int) LRUCache {
head := &LinkNode{0, 0, nil, nil}
tail := &LinkNode{0, 0, nil, nil}
head.next = tail
tail.pre = head
return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
}
func (this *LRUCache) Get(key int) int {
cache := this.m
if v, exist := cache[key]; exist {
this.MoveToHead(v)
return v.val
} else {
return -1
}
}
func (this *LRUCache) RemoveNode(node *LinkNode) {
node.pre.next = node.next
node.next.pre = node.pre
}
func (this *LRUCache) AddNode(node *LinkNode) {
head := this.head
node.next = head.next
head.next.pre = node
node.pre = head
head.next = node
}
func (this *LRUCache) MoveToHead(node *LinkNode) {
this.RemoveNode(node)
this.AddNode(node)
}
func (this *LRUCache) Put(key int, value int) {
tail := this.tail
cache := this.m
if v, exist := cache[key]; exist {
v.val = value
this.MoveToHead(v)
} else {
v := &LinkNode{key, value, nil, nil}
if len(cache) == this.cap {
delete(cache, tail.pre.key)
this.RemoveNode(tail.pre)
}
this.AddNode(v)
cache[key] = v
}
} 因為該算法過于重要，給一個Java版本的：
//java版本
public class LRUCache {
class LinkedNode {
int key;
int value;
LinkedNode prev;
LinkedNode next;
}
private void addNode(LinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(LinkedNode node){
LinkedNode prev = node.prev;
LinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(LinkedNode node){
removeNode(node);
addNode(node);
}
private LinkedNode popTail() {
LinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Hashtable<Integer, LinkedNode> cache = new Hashtable<Integer, LinkedNode>();
private int size;
private int capacity;
private LinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new LinkedNode();
tail = new LinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
LinkedNode node = cache.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
LinkedNode node = cache.get(key);
if(node == null) {
LinkedNode newNode = new LinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if(size > capacity) {
LinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
node.value = value;
moveToHead(node);
}
}
} 第四部分：Redis 近LRU 介紹
上文完成了咱們自己的LRU實作，現在現在聊一聊Redis中的近似LRU。由于真實LRU需要過多的記憶體（在資料量比較大時），是以Redis是使用一種随機抽樣的方式，來實作一個近似LRU的效果。說白了，LRU根本隻是一個預測鍵通路順序的模型。
在Redis中有一個參數，叫做 “maxmemory-samples”，是幹嘛用的呢？
# LRU and minimal TTL algorithms are not precise algorithms but approximated
# algorithms (in order to save memory), so you can tune it for speed or
# accuracy. For default Redis will check five keys and pick the one that was
# used less recently, you can change the sample size using the following
# configuration directive.
#
# The default of 5 produces good enough results. 10 Approximates very closely
# true LRU but costs a bit more CPU. 3 is very fast but not very accurate.
#
maxmemory-samples 5 上面我們說過了，近似LRU是用随機抽樣的方式來實作一個近似的LRU效果。這個參數其實就是作者提供了一種方式，可以讓我們人為幹預樣本數大小，将其設的越大，就越接近真實LRU的效果，當然也就意味着越耗記憶體。（初始值為5是作者預設的最佳）
這個圖解釋一下，綠色的點是新增加的元素，深灰色的點是沒有被删除的元素，淺灰色的是被删除的元素。最下面的這張圖，是真實LRU的效果，第二張圖是預設該參數為5的效果，可以看到淺灰色部分和真實的契合還是不錯的。第一張圖是将該參數設定為10的效果，已經基本接近真實LRU的效果了。
由于時間關系本文基本就說到這裡。那Redis中的近似LRU是如何實作的呢？請關注下一期的内容~
文章來源：本文由小浩算法授權轉載