你面试的时候遇见过LRU吗？

LRU 算法，全称是Least Recently Used。

翻译过来就是最近最少使用算法。

这个算法的思想就是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以，当指定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

听描述你也知道了，它是一种淘汰算法。

这个算法也是面试的一个高频考点。

有的面试官甚至要求手撸一个 LRU 算法出来。

其实我觉得吧，遇到这种情况也不要慌，你就按照自己的思路写一个出来就行。

赌一把，面试官也许自己短时间内都手撸不出来一个无 bug 的 LRU。他也只是检查几个关键点、看看你的代码风格、观察一下你的解题思路而已。

但其实大多数情况下面试场景都是这样的：

面试官：你知道 LRU 算法吗？

我：知道，翻译过来就是最近最少使用算法。其思想是（前面说过，就不复述了）......

面试官：那你能给我谈谈你有哪些方法来实现 LRU 算法呢？

这个时候问的是什么？

问的是：我们都知道这个算法的思路了，请你按照这个思路给出一个可以落地的解决方案。

不用徒手撸一个。

方案一：数组

如果之前完全没有接触过 LRU 算法，仅仅知道其思路。

第一次听就要求你给一个实现方案，那么数组的方案应该是最容易想到的。

假设我们有一个定长数组。数组中的元素都有一个标记。这个标记可以是时间戳，也可以是一个自增的数字。

假设我们用自增的数字。

每放入一个元素，就把数组中已经存在的数据的标记更新一下，进行自增。当数组满了后，就将数字最大的元素删除掉。

每访问一个元素，就将被访问的元素的数字置为 0 。

这不就是 LRU 算法的一个实现方案吗？

按照这个思路，撸一份七七八八的代码出来，问题应该不大吧？

但是这一种方案的弊端也是很明显：需要不停地维护数组中元素的标记。

那么你觉得它的时间复杂度是多少？

是的，每次操作都伴随着一次遍历数组修改标记的操作，所以时间复杂度是O(n)。

但是这个方案，面试官肯定是不会满意的。因为，这不是他心中的标准答案。

也许他都没想过：你还能给出这种方案呢？

但是它不会说出来，只会轻轻的说一句：还有其他的方案吗？

方案二：链表

于是你扣着脑壳想了想。最近最少使用，感觉是需要一个有序的结构。

我每插入一个元素的时候，就追加在数组的末尾。

我每访问一次元素，就把被访问的元素移动到数组的末尾。

这样最近被用的一定是在最后面的，头部的就是最近最少使用的。

当指定长度被用完了之后，就把头部元素移除掉就行了。

这是个什么结构？

这不就是个链表吗？

维护一个有序单链表，越靠近链表头部的结点是越早之前访问的。

当有一个新的数据被访问时，我们从链表头部开始顺序遍历链表。

如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据的对应结点，并将其从原来的位置删除，并插入到链表尾部。

如果此数据没在缓存链表中，怎么办？

分两种情况：

• 如果此时缓存未满，可直接在链表尾部插入新节点存储此数据；
• 如果此时缓存已满，则删除链表头部节点，再在链表尾部插入新节点。

你看，这不又是 LRU 算法的一个实现方案吗？

按照这个思路，撸一份八九不离十的代码出来，问题应该不大吧？

这个方案比数组的方案好在哪里呢？

我觉得就是莫名其妙的高级感，就是看起来就比数组高级了一点。

从时间复杂度的角度看，因为链表插入、查询的时候都要遍历链表，查看数据是否存在，所以它还是O(n)。

总之，这也不是面试官想要的答案。

当你回答出这个方案之后，面试官也许会说：你能不能给我一个查询和插入的时间复杂度都是O(1)的解决方案？

到这里，就得看天分了。

有一说一，如果我之前完全没有接触过 LRU 算法，我可以非常自信的说：

方案三：双向链表+哈希表。

如果我们想要查询和插入的时间复杂度都是O(1)，那么我们需要一个满足下面三个条件的数据结构：

• 1.首先这个数据结构必须是有时序的，以区分最近使用的和很久没有使用的数据，当容量满了之后，要删除最久未使用的那个元素。
• 2.要在这个数据结构中快速找到某个 key 是否存在，并返回其对应的 value。
• 3.每次访问这个数据结构中的某个 key，需要将这个元素变为最近使用的。也就是说，这个数据结构要支持在任意位置快速插入和删除元素。

那么，你说什么样的数据结构同时符合上面的条件呢？

查找快，我们能想到哈希表。但是哈希表的数据是乱序的。

有序，我们能想到链表，插入、删除都很快，但是查询慢。

所以，我们得让哈希表和链表结合一下，成长一下，形成一个新的数据结构，那就是：哈希链表，LinkedHashMap。

这个结构大概长这样：