前言

早在幾年前寫(xiě)過(guò)關(guān)于 LRU cache 的文章：https://crossoverjie.top/2018/04/07/algorithm/LRU-cache/

當(dāng)時(shí)是用 Java 實(shí)現(xiàn)的，最近我在完善 ptg 時(shí)正好需要一個(gè)最近最少使用的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)歷史記錄。

ptg: Performance testing tool (Go), 用 Go 實(shí)現(xiàn)的 gRPC 客戶端調(diào)試工具。

Go 官方庫(kù)中并沒(méi)有相關(guān)的實(shí)現(xiàn)，考慮到程序的簡(jiǎn)潔就不打算依賴第三方庫(kù)，自己寫(xiě)一個(gè)；本身復(fù)雜度也不高，沒(méi)有幾行代碼。

配合這個(gè)數(shù)據(jù)結(jié)構(gòu)，我便在 ptg 中實(shí)現(xiàn)了請(qǐng)求歷史記錄的功能：

將每次的請(qǐng)求記錄存儲(chǔ)到 lru cache 中，最近使用到的歷史記錄排在靠前，同時(shí)也能提供相關(guān)的搜索功能；具體可見(jiàn)下圖。

實(shí)現(xiàn)

實(shí)現(xiàn)原理沒(méi)什么好說(shuō)的，和 Java 的一樣：

• 一個(gè)雙向鏈表存儲(chǔ)數(shù)據(jù)的順序
• 一個(gè) map 存儲(chǔ)最終的數(shù)據(jù)
• 當(dāng)數(shù)據(jù)達(dá)到上限時(shí)移除鏈表尾部數(shù)據(jù)
• 將使用到的 Node 移動(dòng)到鏈表的頭結(jié)點(diǎn)

雖然 Go 比較簡(jiǎn)潔，但好消息是基本的雙向鏈表結(jié)構(gòu)還是具備的。

所以基于此便定義了一個(gè) LruCache:

根據(jù)之前的分析：

• size 存儲(chǔ)緩存大小。
• 鏈表存儲(chǔ)數(shù)據(jù)順序。
• map 存儲(chǔ)數(shù)據(jù)。
• lock 用于控制并發(fā)安全。

接下來(lái)重點(diǎn)是兩個(gè)函數(shù)：寫(xiě)入、查詢。

寫(xiě)入時(shí)判斷是否達(dá)到容量上限，達(dá)到后刪除尾部數(shù)據(jù)；否則就想數(shù)據(jù)寫(xiě)入頭部。

而獲取數(shù)據(jù)時(shí)，這會(huì)將查詢到的結(jié)點(diǎn)移動(dòng)到頭結(jié)點(diǎn)。

這些結(jié)點(diǎn)操作都由 List 封裝好了的。

所以使用起來(lái)也比較方便。

最終就是通過(guò)這個(gè) LruCache 實(shí)現(xiàn)了上圖的效果，想要了解更多細(xì)節(jié)的可以參考源碼:

https://github.com/crossoverJie/ptg/blob/main/gui/lru.go