Redis缓存淘汰策略：LRU算法（最近最少使用）原理与Java实现
一、LRU算法概述
redis缓存淘汰策略-LRU算法（最近最少使用）
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的数据予以淘汰。
二、缓存的基本要求
1. 所谓缓存，必须要有读+写两个操作，按照命中率的思路考虑，写操作+读操作时间复杂度都需要为O(1)。
三、LRU算法的特性要求
2.1必须要有顺序之分，以区分最近使用的和很久没有使用的数据排序。
2.2写和读操作一次搞定。
2.3如果容量（坑位）满了要删除最不常用的数据，每次新访问还要把新的数据插入到队头（按照业务你自己设定左右哪一边是队头）。
查找快、插入快、删除快，且还需要先后排序...
问题：什么样的数据结构可以满足这个问题？你是否可以在O(1)时间复杂度内完成这两种操作？如果一次就可以找到，你觉得什么数据结构最合适？
四、基于LinkedHashMap实现LRU算法
LinkedHashMap是Java中实现LRU算法的理想选择，因为它内部维护了一个双向链表来记录插入顺序或访问顺序。
4.1 核心代码实现
package lru; import java.util.LinkedHashMap; import java.util.Map; public class LRUCacheDemo<K, V> extends LinkedHashMap<K, V> { private int capacity; /** * accessorder the ordering mode * <tt>true</tt> for access-order, * <tt>false</tt> for insertion-order * @param capacity 缓存容量 */ public LRUCacheDemo(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return super.size() > capacity; // return super.removeEldestEntry(eldest); } public static void main(String[] args) { LRUCacheDemo<Integer, String> lruCacheDemo = new LRUCacheDemo<>(3); lruCacheDemo.put(1, "a"); lruCacheDemo.put(2, "b"); lruCacheDemo.put(3, "c"); System.out.println(lruCacheDemo.keySet()); // lruCacheDemo.put(4, "d"); } }4.2 代码执行效果演示
当添加第四个数据进来，这时候就会将1挤出去，淘汰1：
五、关键参数说明
不知道前面有一行代码注意没有？
关键点：super(capacity, 0.75F, false); // true改成了false
这里的第三个参数accessOrder非常重要：
true：按访问顺序排序（LRU模式）false：按插入顺序排序
六、总结
LRU算法通过维护数据的访问顺序来实现缓存淘汰，LinkedHashMap的accessOrder参数设置为true时，可以自动实现LRU特性。当缓存满时，最久未访问的数据会被自动淘汰，保证了缓存中始终是最活跃的数据。
优点：
- 实现简单，利用LinkedHashMap即可
- 时间复杂度为O(1)
- 符合"最近最少使用"的直觉
适用场景：
- Redis缓存淘汰策略
- 浏览器缓存管理
- 数据库查询缓存
- 任何需要缓存淘汰机制的场景