阿里面试，让我十五分钟内手写 LRU。。。

女爷i 2022-12-31 07:22 105阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

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

LRU 算法，全称是Least Recently Used。

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

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

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

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

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

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

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

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

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

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

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

这个时候问的是什么？

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

不用徒手撸一个。

![format_png 2][]

## 方案一：数组 ##

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

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

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

我这里用自增的数字。

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

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

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

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

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

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

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

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

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

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

![format_png 3][]

## 方案二：链表 ##

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

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

等等。

我每访问一个元素，也要把被访问的元素移动到数组的末尾。

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

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

这是个什么结构？

这不就是个链表吗？

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

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

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

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

分两种情况：

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

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

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

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

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

![format_png 4][]

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

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

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

到这里，如果第一次遇到这题，就得看天分了。

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

![format_png 5][]

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

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

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

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

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

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

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

![format_png 6][]

这个结构大概长这样：

![format_png 7][]

借助这个结构，我们再来分析一下上面的三个条件：

>  *  1.如果每次默认从链表尾部添加元素，那么显然越靠近尾部的元素就越是最近使用的。越靠近头部的元素就是越久未使用的。
>  *  2.对于某一个 key ，可以通过哈希表快速定位到链表中的节点，从而取得对应的 value。
>  *  3.链表显示是支持在任意位置快速插入和删除的，修改指针就行。但是单链表无非按照索引快速访问某一个位置的元素，都是需要遍历链表的，所以这里借助哈希表，可以通过 key，快速的映射到任意一个链表节点，然后进行插入和删除。

这才是面试官想要关于 LRU 的正确答案。

但是你以为回答到这里就结束了吗？

面试官为了确认你的掌握程度，还会追问一下。

那么请问：**为什么这里要用双链表呢，单链表为什么不行？**

你心里一慌：我靠，这题我也背过。一时想不起来了。

![format_png 8][]

所以，别只顾着背答案，得理解。

你想啊，我们是不是涉及到删除元素的操作？

那么链表删除元素除了自己本身的指针信息，还需要什么东西？

是不是还需要前驱节点的指针？

那么我们这里要求时间复杂度是O(1)，所以怎么才能直接获取到前驱节点的指针？

这玩意是不是就得上双链表？

咦，你看在一波灵魂追问中，就得到了答案。

面试官的第二个问题又随之而来了：**哈希表里面已经保存了 key ，那么链表中为什么还要存储 key 和 value 呢，只存入 value 不就行了？**

不会，也不要慌，你先分析一波。

刚刚我们说删除链表中的节点，需要借助双链表来实现 O(1)。

删除了链表中的节点，然后呢？

是不是还忘记了什么东西？

是不是还有一个哈希表忘记操作了？

哈希表是不是也得进行对应的删除操作？

删除哈希表需要什么东西？

是不是需要 key，才能删除对应的 value？

这个 key 从哪里来？

是不是只能从链表中的结点里面来？

如果链表中的结点，只有 value 没有 key，那么我们就无法删除哈希表的 key。那不就完犊子了吗？

又是一波灵魂追问。

所以，你现在知道答案了吗？

另外在多说一句，有的小伙伴可能会直接回答借助 LinkedHashMap 来实现。

我觉得吧，你要是实在不知道，也可以这样说。

但是，这个回答可能是面试官最不想听到的回答了。

他会觉得你投机取巧。

但是呢，实际开发中，真正要用的时候，我们还是用的 LinkedHashMap。

而且更多的实际情况是，你开发，写业务代码的时候，根本就不会用到 LRU 算法。

你说这个事情，难受不难受。

![format_png 9][]

好了，你以为到这里面试就结束了？

天真。

## LRU 在 MySQL 中的应用 ##

面试官：小伙子刚刚 LRU 回答的不错哈。要不你给我讲讲，LRU 在 MySQL 中的应用？

LRU 在 MySQL 的应用就是 Buffer Pool，也就是缓冲池。

它的目的是为了减少磁盘 IO。

缓冲池具体是干啥的，我这里就不展开说了。

你就知道它是一块连续的内存，默认大小 128M，可以进行修改。

这一块连续的内存，被划分为若干默认大小为 16KB 的页。

既然它是一个 pool，那么必然有满了的时候，怎么办？

就得移除某些页了，对吧？

那么问题就来了：移除哪些页呢？

刚刚说了，它是为了减少磁盘 IO。所以应该淘汰掉很久没有被访问过的页。

很久没有使用，这不就是 LRU 的主场吗？

但是在 MySQL 里面并不是简单的使用了 LRU 算法。

因为 MySQL 里面有一个预读功能。预读的出发点是好的，但是有可能预读到并不需要被使用的页。

这些页也被放到了链表的头部，容量不够，导致尾部元素被淘汰。

哦豁，降低命中率了，凉凉。

![format_png 10][]

还有一个场景是全表扫描的 sql，有可能直接把整个缓冲池里面的缓冲页都换了一遍，影响其他查询语句在缓冲池的命中率。

那么怎么处理这种场景呢？

把 LRU 链表分为两截，一截里面放的是热数据，一截里面放的是冷数据。

打住，不能再说了。

再说就是另外一篇文章了，点到为止。

你就了解在 MySQL 里面，LRU 是有一个变种的。

如果你不清楚，建议去学习一下哦。

只要你学的够快，你就会被卷的越慢。

## LRU 在 Redis 中的应用 ##

既然是内存淘汰算法，那么我们常用的 Redis 里面必然也有对应的实现。

Redis 的内存淘汰策略有如下几种：

>  *  noenviction：默认策略。不继续执行写请求（DEL 请求可以处理），读请求可以继续进行。
>  *  volatile-lru：从已设置过期时间的数据集中挑选最近最少使用的数据淘汰。没有设置过期时间的 key 不会被淘汰。
>  *  volatile-random：从已设置过期时间的数据集中随机选择数据淘汰。
>  *  volatile-ttl：从已设置过期时间的数据集中挑选将要过期的数据淘汰。
>  *  allkeys-lru：和 volatile-lru 不同的是，这个策略要淘汰的 key 对象是全体的 key 集合。
>  *  allkeys-random：从所有数据集中随机选择数据淘汰。

关于 Redis 中的 LRU 算法，官网上是这样说的：

`https://github.com/redis/redis-doc/blob/master/topics/lru-cache.md`

![format_png 11][]

在 Redis 中的 LRU 算法不是严格的 LRU 算法。

Redis 会尝试执行一个近似的LRU算法，通过采样一小部分键，然后在采样键中回收最适合的那个，也就是最久没有被访问的那个（with the oldest access time）。

然而，从 Redis 3.0 开始，改善了算法的性能，使得更接近于真实的 LRU 算法。做法就是维护了一个回收候选键池。

Redis 的 LRU 算法有一个非常重要的点就是你可以通过修改下面这个参数的配置，自己调整算法的精度。

`maxmemory-samples 5`

而上面截图中，我认为最重要的一句话也已经标志出来了：

`The reason why Redis does not use a true LRU implementation is because it costs more memory.`

Redis 没有使用真实的 LRU 算法的原因是因为这会消耗更多的内存。

然后官网上给了一个随机 LRU 算法和严格 LRU 算法的对比图：

![format_png 12][]

对于这个图官网是这样说的： ![format_png 13][]

你可以从图中看到三种不同的小圆点形成的三个不同的带：

>  *  浅灰色带是被回收（被 LRU 算法淘汰）的对象
>  *  灰色带是没有被回收的对象
>  *  绿色带是新添加的对象

由于 Redis 3.0 对 LRU 算法进行了改进，增加了淘汰池。

所以你可以看到，同样使用 5 个采样点，Redis 3.0 表现得比 Redis 2.8 要好。

同时可以看出，在 Redis 3.0 中使用 10 为采样大小，近似值已经非常接近理论性能。

写到这里我突然想起了另外一个面试题。

**数据库中有 3000w 的数据，而 Redis 中只有 100w 数据，如何保证 Redis 中存放的都是热点数据？**

这个题你说它的考点是什么？

考的就是淘汰策略呀，同志们，只是方式比较隐晦而已。

我们先指定淘汰策略为 allkeys-lru 或者 volatile-lru，然后再计算一下 100w 数据大概占用多少内存，根据算出来的内存，限定 Redis 占用的内存。

接下来的，就交给 Redis 的淘汰策略了。

搞定。

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [计算机专业的学生怎样练习编程才能把编程学精通？][Link 2]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 3]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”，点击左下方阅读原文，获取谷歌师兄的算法刷题笔记。

![format_png 14][]

[format_png]: /images/20221120/ad2e30b24ea942f18ed17815b87295ce.png
[format_png 1]: /images/20221120/1bb945a7b858462aadf941e4eb27dae9.png
[format_png 2]: /images/20221120/da795258b41340638ed9e6d624e9557b.png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU09aeGMyV2liQnRxeFF1Y01PS3Uxam85Q2tpY1VSQWVvOWE1WnVvT0tKOFFMbjN3Q2ljZ2liYVNBZWcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU0plNm4wMHpsMXlvak1iSFJDOHFmcTRFMkFsOGg5cDBtQWdCRFBqZG9PYkRKY3gzbjFVZkVaQS82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU2N0TldMcW1Rcjl3ZTBRZWdKWHNqektGVmljMzZpY2pZSk1sQkluVTRsUXk3MkQ1TFptaHM1akFBLzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU1VwWkhkdmJjUVJoS1p0WVlveVFPenlDakJmSVhwTnZqeG5HcHJNaEdxaWFaT0ZQRm1YVHJMNEEvNjQw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU2Y1aWJtTjNjb25NZmQxNUNRUEN2VlVTSHN1cXc4RFo1cnp1TTluN2lheGJJZkRpY0ZPNXNmQ0VlUS82NDA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU1NESzNWZG5WR2FWcXdJNFNack1vTUU4YlQ3UGFwbVdrNEh0U3FyT1NCc0FyQ1c4WUFPTFFpYmcvNjQw?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU3lwYXBGUldMMnp0dXFvblZQMmFJTUpsMUhoaWNuMEM4WVVDdTlrRTJJcXFhMnVmQnhrRFNYMVEvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU3JORXlOdUtXRmRES3JEdENlaEh2cXhqUWxkM2V0dUVjM1JJRTRGT0JCbVA4TmVpY24xT2lhR2RnLzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZUzRGaWNNbUdlem5BUlE1bGVxM1NObHBJazg2WFhpYU5RWkVmeWc4ZnhFc1cyTUlaUkhoZ2NoOGRBLzY0MA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU0FyNmd5VUN0ZW9pYmRpYUFLQUl0bkNOOHVoa3dWYVdKbzRvdEdoSXZFVmFLS3FHTE5EcEt6cmp3LzY0MA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sbkNxanNRNlFIZHNnc0VOSTNRM1IySVBxNjBoV3FZU1ZLbmoyaWFUelI2eWJJZ3J3cGp4ZUNFVVhsdmJ2MXZtMHRHZDRaM2FDWUQyNlVqQ1M3bEw3OXcvNjQw?x-oss-process=image/format,png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d87aacd7a0ebc3ada34a076d1fa3943ee24097966257132b1042b7a3e4debedc78f38c8cf&idx=1&mid=2247493675&scene=21&sn=6b501ef2032ab911f0a3519eb7397017#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJodm5leUhtTURJTW1sOWtJYlVMUGlhUG5pYThpYW5ic1o3Q2trYlFGQTJLU3V3SzA2R3NuT3JMQ2tleHdwYUVoWU1aNHdac1BpY01Uc1ZBLzY0MA?x-oss-process=image/format,png