10 行 Java 代码实现最近被使用（ LRU ）缓存

（点击 上方公众号 ，可快速关注）

来源：ImportNew - paddx

如有好文章投稿，请点击 → 这里了解详情

在最近的面试中，我曾被多次问到，怎么实现一个最近最少使用（LRU）的缓存。缓存可以通过哈希表来实现，然而为这个缓存增加大小限制会变成另一个有意思的问题。现在我们看一下怎么实现。

最近最少使用缓存的回收

为了实现缓存回收，我们需要很容易做到：

• 查询出最近最晚使用的项

• 给最近使用的项做一个标记

链表可以实现这两个操作。检测最近最少使用的项只需要返回链表的尾部。标记一项为最近使用的项只需要从当前位置移除，然后将该项放置到头部。比较困难的事情是怎么快速的在链表中找到该项。

哈希表的帮助

看一下我们工具箱中的数据结构，哈希表可以在（消耗）常量的时间内索引到某个对象。如果我们创建一个形如key->链表节点的哈希表，我们就能够在常量时间内找到最近使用的节点。更甚的是，我们也能够在常量时间内判断节点的是否存在（或不存在）；