LRU原理
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
- 最常见的实现是使用一个链表保存缓存数据，详细算法实现如下
- 新数据插入到链表头部；
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
-
当链表满的时候，将链表尾部的数据丢弃。
【命中率】
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。
代码实现
很多编程语言都有内置的哈希链表或者类似 LRU 功能的库函数，但是为了帮大家理解算法的细节，我们用 Java 自己造轮子实现一遍 LRU 算法。
首先，我们把双链表的节点类写出来，为了简化，key 和 val 都认为是 int 类型：
class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
然后依靠我们的 Node 类型构建一个双链表，实现几个要用到的 API，这些操作的时间复杂度均为 O(1) ：
class DoubleList {
// 在链表头部添加节点 x
public void addFirst(Node x);
// 删除链表中的 x 节点（x 一定存在）
public void remove(Node x);
// 删除链表中最后一个节点，并返回该节点
public Node removeLast();
// 返回链表长度
public int size();
}
PS：这就是普通双向链表的实现，为了让读者集中精力理解 LRU 算法的逻辑，就省略链表的具体代码。
到这里就能回答刚才“为什么必须要用双向链表”的问题了，因为我们需要删除操作。删除一个链表节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。
有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚:
如果能够看懂上述逻辑，翻译成代码就很容易理解了：