【redis前傳】自己手寫一個LRU政策 | redis淘汰政策

title: 自己手寫一個LRU政策

date: 2021-06-18 12:00:30

tags:

- [redis]

- [lru]

categories:

- [redis]

permalink: zxh

prefix: redis

一、題目描述

146. LRU 緩存機制

運用你所掌握的資料結構，設計和實作一個

LRU

(最近最少使用) 緩存機制 。

實作

LRUCache

類：

LRUCache(int capacity)

以正整數作為容量 capacity 初始化

LRU

緩存

int get(int key) 如果關鍵字 key 存在于緩存中，則傳回關鍵字的值，否則傳回 -1 。

void put(int key, int value) 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新資料之前删除最久未使用的資料值，進而為新的資料值留出空間。

進階：你是否可以在 O(1) 時間複雜度内完成這兩種操作？

二、思路分析

第一想法

• 剛看到本題時沒有多想就覺得會用到隊列，因為隊列FIFO可以做到淘汰末尾資料，但是仔細一想本題是需要淘汰最近最少使用資料，如果僅僅是最近的資料那麼隊列很容易實作。加上使用頻率就涉及到資料的頻繁挪動。很明顯隊列是無法完成的。
• 那麼有沒有一種順序添加的資料，每次在擷取之後就會将資料前移至一端呢？答案是有的！

  LinkedHashMap

• LinkedHashMap

  不熟悉的朋友們可以簡單的将它了解成

  HashMap

  。 下圖展示了

  HashMap

  的存儲結構

• 上述的元素我這裡做了個動畫示範全過程！！！

• 而

  LinkedHashMap

  隻是多了一條連結清單串起裡面的元素

• 這也是為什麼

  LinkedHashMap

  是按照順序存儲的。但是

  LinkedHahsMap

  也無法做到按照使用頻率進行排序啊？大家都知道他是按照添加順序排序的！！！

LinkedHashMap

改造

• 原生的

  LinkedHashMap

  的确無法滿足情況，但是我們稍微看下源碼能夠發現在put之後都會執行下

  afterNodeInsertion

  這個方法。這也是

  HashMap

  留給

  LinkedHashMap

  做的擴充！

• removeNode

  就是将最前面的資料。想要進入這個方法就需要

  removeEldestEntry

  判斷。

  LinkedHashMap

  預設是false . 是以我們隻需要重寫他就行了。但是還是在get值的時候如何保值在最後面呢？我們仔細看下源碼就能夠發現在

  get

  中有這個一個方法

  afterNodeAccess

  。他的作用就是将get的元素移位值後面。正好符合我們

  LRU

  的政策特征

• 綜上！我們借助

  LinkedHashMap

  就非常容易的實作了LRU政策！

自己實作

• 但是本題的意思是想考察我們自己是如何實作的，而不是巧妙對現有的工具改造的！不過上面對

  LinkedHashMap

  的确改造的很巧這是不可否認的！下面我們就嘗試自己來實作下這種方式！
• 首先我們需要确定需要用到Hash結合連結清單來實作。Hash我們自然使用

  HashMap

  來存儲資料為的就是友善定位資料。定位到資料就需要操作連結清單将資料實時移位值連結清單尾部，每次淘汰是将連結清單首位移除既可。為了友善我們操作連結清單這裡的連結清單肯定是雙連結清單的！

連結清單單元

• 首先我們定義一個内部類！用于連結清單的基本單元。裡面存儲了key,value友善根據Hash中存儲的内容找到節點！

  preNode

  ，

  nextNode

  分别指向前後節點

• 在建構器中初始化容量和連結清單大小，并初始化邊界節點友善我們操作節點中移位和删除。

• 在擷取資料時沒有添加就傳回-1 ， 已經添加的資料則将該資料對應的node節點移動到連結清單的尾部。

• 在put中當第一次添加我們需要維護連結清單大小并進行檢測是否需要進行淘汰資料，如果不是第一次添加我們隻需奧更新值和對應node在連結清單中的位置即可

方法名	作用
addToTail	将節點添加值連結清單尾部
moveToTail	将已經存在于連結清單中的節點移動到連結清單的尾部
removeHeadNode	删除連結清單中第一個節點，注意是邊界節點後第一個節點

四、總結

• 雖然執行時間和記憶體消耗有點高！但是我就是不優化。
• 本題主要就是在連結清單的移動上面會複雜點。我們需要按照添加順序和使用頻率兩個次元進行維護他們之間的順序。隻要這個順序維護好，就沒啥問題了！