LRU 缓存淘汰

LRU 是 Last Recently Used 的缩写，即最近最少使用，是一种常用的置换算法，选择最近最久未使用的数据予以淘汰。

缓存结构

• 图中存在两条链表，其中的双向链表用于记录 LRU 访问，当 data 被访问时，对应的节点就移动到链表尾部，表示最近访问。
• 另一条链表 hnext 用于记录在散列表中的拉链。
• 查找数据：散列表中查找数据的时间复杂度接近 O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找到数据之后，我们还需要将它移动到双向链表的尾部。
• 删除数据：找到数据所在的结点，然后将结点删除。借助散列表，我们可以在 O(1) 时间复杂度里找到要删除的结点。因为我们的链表是双向链表，双向链表可以通过前驱指针 O(1) 时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要 O(1) 的时间复杂度。
• 添加数据：先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾部。

Java LinkedHashMap

Java 中的 LinkedHashMap 就是典型的一个 LRU 缓存系统。

// 10 是初始大小，0.75 是装载因子，true 是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
 
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());  // 打印 3, 1, 5, 2
}

m.put(3, 26);
m.get(5);
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());  // 1, 2, 3, 5
}

这里一开始，插入之后在内存中组织为 3，1，5，2 的双向链表结构，然后插入 3，将会更新 3 的值，并将3移动到链表最尾，最后一次访问的key是 5，所以最终打印为 1，2，3，5。