用 Go 實作一個 LRU cache

前言

早在幾年前寫過關于

LRU cache

的文章：

https://crossoverjie.top/2018/04/07/algorithm/LRU-cache/

當時是用 Java 實作的，最近我在完善 ptg 時正好需要一個最近最少使用的資料結構來存儲曆史記錄。

ptg: Performance testing tool (Go), 用 Go 實作的 gRPC 用戶端調試工具。

Go 官方庫中并沒有相關的實作，考慮到程式的簡潔就不打算依賴第三方庫，自己寫一個；本身複雜度也不高，沒有幾行代碼。

配合這個資料結構，我便在 ptg 中實作了請求曆史記錄的功能：

将每次的請求記錄存儲到 lru cache 中，最近使用到的曆史記錄排在靠前，同時也能提供相關的搜尋功能；具體可見下圖。

實作

實作原理沒什麼好說的，和

Java

的一樣：

• 一個雙向連結清單存儲資料的順序
• 一個

  map

  存儲最終的資料
• 當資料達到上限時移除連結清單尾部資料
• 将使用到的

  Node

  移動到連結清單的頭結點

雖然 Go 比較簡潔，但好消息是基本的雙向連結清單結構還是具備的。

是以基于此便定義了一個

LruCache

:

根據之前的分析：

• size

  存儲緩存大小。
• 連結清單存儲資料順序。

• map

  存儲資料。

• lock

  用于控制并發安全。

接下來重點是兩個函數：寫入、查詢。

寫入時判斷是否達到容量上限，達到後删除尾部資料；否則就想資料寫入頭部。

而擷取資料時，這會将查詢到的結點移動到頭結點。

這些結點操作都由 List 封裝好了的。

是以使用起來也比較友善。

最終就是通過這個

LruCache

實作了上圖的效果，想要了解更多細節的可以參考源碼:

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

作者：

crossoverJie

出處：

https://crossoverjie.top

歡迎關注部落客公衆号與我交流。

本文版權歸作者所有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出,

如有問題， 可郵件（crossoverJie#gmail.com）咨詢。