一、誕生原因

緩存是一種提供數據讀取性能的技術，在硬件設計、軟件開發中有廣泛的應用，比如常見的 CPU 緩存，DB 緩存和瀏覽器緩存等。但是緩存的大小是有限的，需要一定的機制判斷哪些數據需要淘汰，即：移出緩存，從而保證緩存中的數據始終是常用的。常用的機制里面包括 LRU 緩存淘汰算法。

二、設計原則

全稱：Least?Recently Used

如果一個數據在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。所以淘汰的數據應該是許久沒有訪問到的數據。

三、所用的數據結構

雙向鏈表：用于串聯緩存數據。

紅黑樹（散列表）：用于索引緩存數據。

四、執行過程

假設 data 中包含 key 和 value。

節點為 node（指針）。

1、增加緩存數據時，

若緩存已滿，double list 尾部數據 delete 掉，將新 data 壓入雙向鏈表頭部；

將新 data 壓入到紅黑樹中，key 值為 data 中的 key，value 為 node。

2、獲取緩存數據時，

先從紅黑樹中根據 key 找到 node，將 node 放到雙向鏈表的頭部，最后返回 node 中 data。

五、代碼栗子

github

六、優化

節選：https://www.cnblogs.com/goodAndyxublog/p/11757134.html

以下方案來源與 MySQL InnoDB LRU 改進算法

將鏈表拆分成兩部分，分為熱數據區，與冷數據區，如圖所示。

改進之后算法流程將會變成下面一樣:

訪問數據如果位于熱數據區，與之前 LRU 算法一樣，移動到熱數據區的頭結點。

插入數據時，若緩存已滿，淘汰尾結點的數據。然后將數據插入冷數據區的頭結點。

處于冷數據區的數據每次被訪問需要做如下判斷：

• 若該數據已在緩存中超過指定時間，比如說 1 s，則移動到熱數據區的頭結點。
• 若該數據存在在時間小于指定的時間，則位置保持不變。

對于偶發的批量查詢，數據僅僅只會落入冷數據區，然后很快就會被淘汰出去。熱門數據區的數據將不會受到影響，這樣就解決了 LRU 算法緩存命中率下降的問題。

?

參考：極客時間《數據結構與算法之美》王爭

這門課真心推薦，內容很經典、栗子很形象，里面還包含了很多面試題目。真是居家旅行必備良藥。

?

（SAW：Game Over！）

總結

以上是生活随笔為你收集整理的数据结构与算法 / LRU 缓存淘汰算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。