前言

早在几年前写过对于 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