最近在折腾一些小项目，让我突然有了一些对 LRU map 的想法
一般常见的 LRU map 的实现大概是长这样
通过一个 HashMap 来实现对值的快速访问，但是 Map 中记录的值并不是原始的值， 当然也有可能包含原始的值，但是至少会记录一个链表的节点地址
每次进行读取/写入操作的时候， 需要将对应链表的那个节点，移动到链表的尾部
当需要进行逐出值的时候，就从链表的头部取出值进行逐出，因为链表的头处的值必然是最久没有访问过的值了
最近想到了一种新的解决 LRU map 的方法，即不再需要链表来做关联映射。而是准备一个队列。HashMap 中的值不再携带链表的地址，而是记录实际的最后访问时间
每次进行读取/写入操作的时候，都修改 HashMap 中的此节点的最后操作时间，然后同时将这次读取/写入操作的 key 和时间写入队列
每次需要逐出值的时候，就重复从队列里取值，然后判断一下队列中节点记录的操作时间和实际在 HashMap 中的时间是否一致，如果一致的话那就可以逐出，否则就不逐出，继续从队列中取值
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。