借助这个结构，我们再来分析一下上面的三个条件：
- 1.如果每次默认从链表尾部添加元素，那么显然越靠近尾部的元素就越是最近使用的。越靠近头部的元素就是越久未使用的。
- 2.对于某一个 key ，可以通过哈希表快速定位到链表中的节点，从而取得对应的 value。
- 3.链表显然是支持在任意位置快速插入和删除的，修改指针就行。但是单链表无法按照索引快速访问某一个位置的元素，都是需要遍历链表的，所以这里借助哈希表，可以通过 key，快速的映射到任意一个链表节点，然后进行插入和删除。
这才是面试官想要关于 LRU 的正确答案。
但是你以为回答到这里就结束了吗？
面试官为了确认你的掌握程度，还会追问一下。
那么请问：为什么这里要用双链表呢，单链表为什么不行？
你心里一慌：我靠，这题我也背过。一时想不起来了。
所以，别只顾着背答案，得理解。
你想啊，我们是不是涉及到删除元素的操作？
那么链表删除元素除了自己本身的指针信息，还需要什么东西？
是不是还需要前驱节点的指针？
那么我们这里要求时间复杂度是O(1)，所以怎么才能直接获取到前驱节点的指针？
这玩意是不是就得上双链表？
咦，你看在一波灵魂追问中，就得到了答案。
面试官的第二个问题又随之而来了：哈希表里面已经保存了 key ，那么链表中为什么还要存储 key 和 value 呢，只存入 value 不就行了？
不会也不要慌，你先分析一波。
刚刚我们说删除链表中的节点，需要借助双链表来实现O(1)。
删除了链表中的节点，然后呢？
是不是还忘记了什么东西？
是不是还有一个哈希表忘记操作了？
哈希表是不是也得进行对应的删除操作？
删除哈希表需要什么东西？
是不是需要 key，才能删除对应的 value？
这个 key 从哪里来？
是不是只能从链表中的结点里面来？
如果链表中的结点，只有 value 没有 key，那么我们就无法删除哈希表的 key。那不就完犊子了吗？
又是一波灵魂追问。
所以，你现在知道答案了吗？
另外在多说一句，有的小伙伴可能会直接回答借助 LinkedHashMap 来实现。
我觉得吧，你要是实在不知道，也可以这样说。
但是，这个回答可能是面试官最不想听到的回答了。
他会觉得你投机取巧。
但是呢，实际开发中，真正要用的时候，我们还是用的 LinkedHashMap。
你说这个事情，难受不难受。
好了，你以为到这里面试就结束了？
LRU 在 MySQL 中的应用
面试官：小伙子刚刚 LRU 回答的不错哈。要不你给我讲讲，LRU 在 MySQL 中的应用？
LRU 在 MySQL 的应用就是 Buffer Pool，也就是缓冲池。
它的目的是为了减少磁盘 IO。
缓冲池具体是干啥的，我这里就不展开说了。
你就知道它是一块连续的内存，默认大小 128M，可以进行修改。
这一块连续的内存，被划分为若干默认大小为 16KB 的页。
既然它是一个 pool，那么必然有满了的时候，怎么办？
就得移除某些页了，对吧？
那么问题就来了：移除哪些页呢？
刚刚说了，它是为了减少磁盘 IO。所以应该淘汰掉很久没有被访问过的页。
很久没有使用，这不就是 LRU 的主场吗？
但是在 MySQL 里面并不是简单的使用了 LRU 算法。
因为 MySQL 里面有一个预读功能。预读的出发点是好的，但是有可能预读到并不需要被使用的页。
这些页也被放到了链表的头部，容量不够，导致尾部元素被淘汰。
哦豁，降低命中率了，凉凉。
还有一个场景是全表扫描的 sql，有可能直接把整个缓冲池里面的缓冲页都换了一遍，影响其他查询语句在缓冲池的命中率。
那么怎么处理这种场景呢？
把 LRU 链表分为两截，一截里面放的是热数据，一截里面放的是冷数据。
打住，不能再说了。
再说就是另外一篇文章了，点到为止。
如果你不清楚，建议去学习一下哦。
LRU 在 Redis 中的应用
既然是内存淘汰算法，那么我们常用的 Redis 里面必然也有对应的实现。
Redis 的内存淘汰策略有如下几种：
- noenviction：默认策略。不继续执行写请求（DEL 请求可以处理），读请求可以继续进行。这样可以保证不会丢失数据，但是会让线上的业务不能持续进行。
- volatile-lru：从已设置过期时间的数据集中挑选最近最少使用的数据淘汰。没有设置过期时间的 key 不会被淘汰。
- volatile-random：从已设置过期时间的数据集中随机选择数据淘汰。
- volatile-ttl：从已设置过期时间的数据集中挑选将要过期的数据淘汰。
- allkeys-lru：和 volatile-lru 不同的是，这个策略要淘汰的 key 对象是全体的 key 集合。
- allkeys-random：从所有数据集中随机选择数据淘汰。
Redis 4.0 之后，还增加了两个淘汰策略。
