在最近的采访中，我多次被问到如何实现最近最少使用(LRU)缓存。可以使用哈希表实现缓存，但是向该缓存添加大小限制成为另一个有趣的问题。现在让我们看看如何去做。最近最少使用缓存的回收为了实现缓存回收，我们需要很容易做到：查询最近使用的item标记最近使用的item链表可以实现这两个操作。检测最近最少使用的项目只需要返回链表的尾部。将一个项目标记为最近使用只是将其从当前位置移除并将该项目放在头部。比较难的是如何快速找到链表中的item。哈希表帮助查看我们工具箱中的数据结构，哈希表可以在（消耗）常数时间内索引到一个对象。如果我们创建一个key->linklistnode形式的哈希表，我们可以在常数时间内找到最近使用的节点。更重要的是，我们还可以在常数时间内判断节点是否存在（或不存在）；找到这个节点后，我们可以把这个节点移到链表的前面，标记为最近使用的项。Java中的快捷键据我所知，在编程语言的标准库中很少有常见的数据结构可以提供上述功能。这是一个混合数据结构，我们需要在哈希表的基础上构建一个链表。但是Java已经为我们提供了这种形式的数据结构——LinkedHashMap！它甚至提供了覆盖回收策略的方法（请参阅removeEldestEntry文档）。***需要注意的是，改变链表的顺序是插入的顺序，不是访问的顺序。但是，有一个构造函数提供了使用访问顺序的选项（请参阅文档）。不用说了：importjava.util.LinkedHashMap;importjava.util.Map;publicLRUCache
