一、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 * &lt;tt&gt;true&lt;/tt&gt; for access-order, * &lt;tt&gt;false&lt;/tt&gt; for insertion-order * @param capacity 缓存容量 */ public LRUCacheDemo(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry&lt;K, V&gt; eldest) { return super.size() &gt; capacity; // return super.removeEldestEntry(eldest); } public static void main(String[] args) { LRUCacheDemo&lt;Integer, String&gt; lruCacheDemo = new LRUCacheDemo&lt;&gt;(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缓存淘汰策略
• 浏览器缓存管理
• 数据库查询缓存
• 任何需要缓存淘汰机制的场景