緩存淘汰演算法--LRU演算法

一個用hash表作為底層結構的資料庫，當然少不了緩存淘汰演算法。

LRU（Least recently used，最近最少使用）演算法根據數據的歷史訪問記錄來進行淘汰數據，其核心思想是「如果數據最近被訪問過，那麼將來被訪問的幾率也更高」。

1. 新數據插入到鏈表頭部；
2. 每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部；
3. 當鏈表滿的時候，將鏈表尾部的數據丟棄。

過程如下：

1. 最開始時，內存空間是空的，因此依次進入A、B、C是沒有問題的
2. 當加入D時，就出現了問題，內存空間不夠了，因此根據LRU演算法，內存空間中A待的時間最為久遠，選擇A,將其淘汰
3. 當再次引用B時，內存空間中的B又處於活躍狀態，而C則變成了內存空間中，近段時間最久未使用的
4. 當再次向內存空間加入E時，這時內存空間又不足了，選擇在內存空間中待的最久的C將其淘汰出內存，這時的內存空間存放的對象就是E->B->D

附上：golang演算法

package lruimport "container/list"type LRUCache struct { capacity int cache map[int]*list.Element list *list.List}type Pair struct { key int value int}func Constructor(capacity int) LRUCache { return LRUCache{ capacity: capacity, list: list.New(), cache: make(map[int]*list.Element), }}func (this *LRUCache) Get(key int) int { if elem, ok := this.cache[key]; ok { this.list.MoveToFront(elem) return elem.Value.(Pair).value } return -1}func (this *LRUCache) Put(key int, value int) { if elem, ok := this.cache[key]; ok { this.list.MoveToFront(elem) elem.Value = Pair{key, value} } else { if this.list.Len() >= this.capacity { delete(this.cache,this.list.Back().Value.(Pair).key) this.list.Remove(this.list.Back()) } this.list.PushFront(Pair{key, value}) this.cache[key] = this.list.Front() }}

LRU其實還可以再優化，用過redis的都知道可以過期時間，在LRUCache數據結構裡面設置TTL過期時間也是可以的，詳細的自己慢慢實現吧。

演算法鏈接： github