動手實現一個 LRU cache

前言

LRU 是 的簡寫，字面意思則是 。

通常用於緩存的淘汰策略實現，由於緩存的內存非常寶貴，所以需要根據某種規則來剔除數據保證內存不被撐滿。

如常用的 Redis 就有以下幾種策略：

摘抄自:https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Redis.md#%E5%8D%81%E4%B8%89%E6%95%B0%E6%8D%AE%E6%B7%98%E6%B1%B0%E7%AD%96%E7%95%A5

實現一

之前也有接觸過一道面試題，大概需求是：

實現一個 LRU 緩存，當緩存數據達到 N 之後需要淘汰掉最近最少使用的數據。

N 小時之內沒有被訪問的數據也需要淘汰掉。

以下是我的實現：

感興趣的朋友可以直接從:

https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUAbstractMap.java

下載代碼本地運行。

代碼看著比較多，其實實現的思路還是比較簡單：

採用了與 HashMap 一樣的保存數據方式，只是自己手動實現了一個簡易版。

內部採用了一個隊列來保存每次寫入的數據。

寫入的時候判斷緩存是否大於了閾值 N，如果滿足則根據隊列的 FIFO 特性將隊列頭的數據刪除。因為隊列頭的數據肯定是最先放進去的。

再開啟了一個守護線程用於判斷最先放進去的數據是否超期（因為就算超期也是最先放進去的數據最有可能滿足超期條件。）

設置為守護線程可以更好的表明其目的（最壞的情況下，如果是一個用戶線程最終有可能導致程序不能正常退出，因為該線程一直在運行，守護線程則不會有這個情況。）

以上代碼大體功能滿足了，但是有一個致命問題。

就是最近最少使用沒有滿足，刪除的數據都是最先放入的數據。

不過其中的 流程算是一個簡易的 HashMap 實現，可以對 HashMap 加深一些理解。

實現二

因此如何來實現一個完整的 LRU 緩存呢，這次不考慮過期時間的問題。

其實從上一個實現也能想到一些思路：

要記錄最近最少使用，那至少需要一個有序的集合來保證寫入的順序。

在使用了數據之後能夠更新它的順序。

基於以上兩點很容易想到一個常用的數據結構：鏈表。

每次寫入數據時將數據放入鏈表頭結點。

使用數據時候將數據移動到頭結點。

緩存數量超過閾值時移除鏈表尾部數據。

因此有了以下實現：

源碼： https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUMap.java

實際效果，寫入時：

使用時：

實現思路和上文提到的一致，說下重點：

數據是直接利用 HashMap 來存放的。

內部使用了一個雙向鏈表來存放數據，所以有一個頭結點 header，以及尾結點 tailer。

每次寫入頭結點，刪除尾結點時都是依賴於 header tailer，如果看著比較懵建議自己實現一個鏈表熟悉下，或結合下文的對象關係圖一起理解。

使用數據移動到鏈表頭時，第一步是需要在雙向鏈表中找到該節點。這裡就體現出鏈表的問題了。查找效率很低，最差需要 。之後依賴於當前節點進行移動。

在寫入頭結點時有判斷鏈表大小等於 2 時需要刪除初始化的頭尾結點。這是因為初始化時候生成了兩個雙向節點，沒有數據只是為了形成一個數據結構。當真實數據進來之後需要刪除以方便後續的操作（這點可以繼續優化）。

以上的所有操作都是線程不安全的，需要使用者自行控制。

下面是對象關係圖：

初始化時

寫入數據時

獲取數據時

數據和上文一樣：

通過以上幾張圖應該是很好理解數據是如何存放的了。

實現三

其實如果對 Java 的集合比較熟悉的話，會發現上文的結構和 LinkedHashMap 非常類似。

對此不太熟悉的朋友可以先了解下 LinkedHashMap 底層分析 。

所以我們完全可以藉助於它來實現：

源碼： https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRULinkedMap.java

這次就比較簡潔了，也就幾行代碼（具體的邏輯 LinkedHashMap 已經幫我們實現好了）

實際效果:

使用時：

LinkedHashMap 內部也有維護一個雙向隊列，在初始化時也會給定一個緩存大小的閾值。初始化時自定義是否需要刪除最近不常使用的數據，如果是則會按照實現二中的方式管理數據。

其實主要代碼就是重寫了 LinkedHashMap 的 removeEldestEntry 方法:

它默認是返回 false，也就是不會管有沒有超過閾值。

所以我們自定義大於了閾值時返回 true，這樣 LinkedHashMap 就會幫我們刪除最近最少使用的數據。

總結

以上就是對 LRU 緩存的實現，了解了這些至少在平時使用時可以知其所以然。

當然業界使用較多的還有 guava 的實現，並且它還支持多種過期策略。

號外

最近在總結一些 Java 相關的知識點，感興趣的朋友可以一起維護。

地址: https://github.com/crossoverJie/Java-Interview

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！