redis 的 LRU 算法简介
题目：1、redis 的 lru 了解过吗？是否可以手写一个 lru 算法？
什么是 LRU？
LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法。
选择最近最久未使用的数据予以淘汰。
算法设计来源
力扣（146 题目 LRU 算法简介）：
如图：
设计思想
1、所谓缓存，必须要有读 + 写两个操作，按照命中率的思路考虑，写操作 + 读操作时间复杂度都需要为 O(1)。
2、 特征要求
2.1 必须要有顺序之分，一区分最近使用的和很久没有使用的数据排序。
2.2 写和读操作一次执行。
2.3 如果容量（坑位）满了要删除最不长用的谁，每次新访问还要把新的数据出入到队头（按照业务你自己设定左右那一边是队头）。
查找快、插入快、删除快、且还要先后排序 -----> 什么样的数据结构可以满足这个问题？
你是否可以在 O(1) 的时间复杂度内完成这两种操作？
如果一次就可以找到，你觉得什么数据结构最合适？？？
LRU 的算法核心是哈希链表
本质就是 HashMap + DoubleLinkedList
时间复杂是O(1) ，哈希+双向链表的结合体。
LRU 算法动画
LRU 手动编码实现
实现案例一
参考： LinkedHashMap
依赖 jdk
public class Q149<K, V> extends LinkedHashMap<K, V> { private int capacity; // 缓存坑位 public Q149(int capacity) { // true 是访问顺序 // false 是插入顺序 super(capacity, 0.75F, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return super.size() > capacity; } public static void main(String[] args) { Q149 q149 = new Q149(3); q149.put(1, "a"); q149.put(2, "b"); q149.put(3, "c"); System.out.println(q149.keySet()); q149.put(4, "d"); q149.put(5, "e"); System.out.println(q149.keySet()); } }
