LRU 的来源

LRU（Least Recently Used），近期最少使用算法，常应用于缓存中的数据淘汰，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高“。

基于数组实现

仔细看下这个算法的定义：近期最少使用算法，其实就是按照”近期最少使用”这个条件去淘汰相应的数据。

既然是淘汰最近最少使用的数据，姑且就可以理解为，当内存满了的那个时刻，内存中，哪些数据最后一次被访问的时间最小，不表示哪些数据是冷数据，应该被移除。

假如每条数据有一个属性lasttime，用来记录被访问时刻的时间，这样，每一条数据都有一个最后访问时间，当内存满的时候，遍历所有元素，删除最后访问时间最小的那个元素：

lasttime = current_time()
lastKey = null;
if list full:
    foreach each item of list:
        if item.lasttime < lasttime:
            lasttime = item.lasttime
            lastKey = item.key

然后把lastKey指向的那条数据删除。

性能分析

这个算法是可行的。但是，当内存满时，删除最近最长时间未被使用元素的平均时间复杂度为 O(n)，因为，我们需要先找到 lasttime 为最小的数据元素，将其删除，再将这个数据元素之后的元素向前移动一格。

试想一下，假如有一千万条数据，每次删除都需要找出访问时间最早的那些数据，这是很耗资源的操作，时间复杂度是O(N)，跟数据量成正比，数据量越大，性能越低。

不仅如此，查找一个数据元素的时间复杂度也是O(N)。

基于双向链表的实现

基于以上不足，我们可以通过使用链表来实现，这样，当缓存中数据元素的个数，超过阈值时，“删除最近最久未使用元素”操作的时间复杂度仅为 O(1)：

每次写入数据时，将数据放入链表头结点，时间复杂度为 O(1)。
使用缓存中数据时，将数据移动到头结点，时间复杂度为 O(n)。
缓存数量超过阈值时，移除链表尾部数据，时间复杂度为 O(1)。

这个算法同样是可行的。但是，问题在于“使用缓存中数据时，将数据移动到头结点”操作的时间复杂度为 O(n)。

基于双向链表 + Hashmap 的实现

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

对于 get 操作，首先判断 key 是否存在：
- 如果 key 不存在，则返回 −1；
- 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
对于 put 操作，首先判断 key 是否存在：
- 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。

Tip

在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

复杂度分析

时间复杂度：对于 put 和 get 都是 O(1)。

空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。

Reference

LRU算法的原理和实现 - http://dongyado.com/algorithm/funny/2016/04/23/implement-lru-cache-by-yourself/
LRU算法四种实现方式介绍 - https://blog.csdn.net/elricboa/article/details/78847305
看动画理解「链表」实现LRU缓存淘汰算法 - https://cxyxiaowu.com/articles/2019/04/04/1554345296887.html
https://talkgo.org/t/topic/2280

【Cache System】LRU（Least Recently Used）算法