仓库源文，站点原文

title: 关于 LRU map 的一些灵感 date: 2023-12-18 08:38:05 updated: 2023-12-18 08:38:05 categories:

• 杂项 tag:
• 随想
• 缓存 description: 关于 LRU map 的新的想法，虽然并不一定有效或者说效果更好，这里也就是给自己留个念头，也许后续会找个时间验证一下 mermaid: true

最近在折腾一些小项目，让我突然有了一些对 LRU map 的想法

传统的 LRU map 的实现

一般常见的 LRU map 的实现大概是长这样

通过一个 HashMap 来实现对值的快速访问，但是 Map 中记录的值并不是原始的值， 当然也有可能包含原始的值，但是至少会记录一个链表的节点地址

每次进行读取/写入操作的时候， 需要将对应链表的那个节点，移动到链表的尾部

当需要进行逐出值的时候，就从链表的头部取出值进行逐出，因为链表的头处的值必然是最久没有访问过的值了

一些新的想法

最近想到了一种新的解决 LRU map 的方法，即不再需要链表来做关联映射。而是准备一个队列。HashMap 中的值不再携带链表的地址，而是记录实际的最后访问时间

每次进行读取/写入操作的时候，都修改 HashMap 中的此节点的最后操作时间，然后同时将这次读取/写入操作的 key 和时间写入队列

每次需要逐出值的时候，就重复从队列里取值，然后判断一下队列中节点记录的操作时间和实际在 HashMap 中的时间是否一致，如果一致的话那就可以逐出，否则就不逐出，继续从队列中取值