前言
早在幾年前寫(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é)的可以參考源碼:
