LRU算法本地实现

方法一基于LinkedHashMap实现LRU使用LinkedHashMap实现 LRU最近最少使用缓存非常简单因为LinkedHashMap本身提供了按访问顺序排序和移除最老条目的钩子方法。实现原理构造LinkedHashMap时设置accessOrdertrue这样每次调用get或put时被访问的条目会被移动到链表的末尾链表头部就是最久未使用的条目。重写removeEldestEntry方法当Map大小超过设定的最大容量时返回trueLinkedHashMap就会自动移除头部的最老的条目。代码示例importjava.util.LinkedHashMap;importjava.util.Map;publicclassLRUCacheK,VextendsLinkedHashMapK,V{privatefinalintmaxCapacity;/** * 构造 LRU 缓存 * param maxCapacity 最大容量 */publicLRUCache(intmaxCapacity){// 初始容量默认16负载因子0.75accessOrdertrue 表示按访问顺序排序super(16,0.75f,true);this.maxCapacitymaxCapacity;}/** * 当 Map 大小超过最大容量时移除最老的条目 * param eldest 最老的条目 * return 是否移除该条目 */OverrideprotectedbooleanremoveEldestEntry(Map.EntryK,Veldest){returnsize()maxCapacity;}// 测试代码publicstaticvoidmain(String[]args){LRUCacheInteger,StringcachenewLRUCache(3);cache.put(1,A);cache.put(2,B);cache.put(3,C);System.out.println(cache);// {1A, 2B, 3C}// 访问 1它会被移动到末尾cache.get(1);System.out.println(cache);// {2B, 3C, 1A}// 插入新条目此时容量超限移除最老的 2cache.put(4,D);System.out.println(cache);// {3C, 1A, 4D}}}关键点说明super(16, 0.75f, true)第三个参数true表示启用“访问顺序”而非默认的插入顺序。removeEldestEntry每次put之后会自动调用该方法判断是否需要移除头部最老的条目。这里直接比较当前大小与最大容量。线程不安全上述实现不是线程安全的如果需要在多线程环境下使用可以包装为Collections.synchronizedMap或者使用ConcurrentLinkedHashMap第三方库。扩展泛型与线程安全版本如果需要线程安全可以这样包装LRUCacheInteger,StringcachenewLRUCache(3);MapInteger,StringsynchronizedCacheCollections.synchronizedMap(cache);但注意removeEldestEntry的调用会在同步块内部自动处理。方法二基于 Guava Cache 和 Caffeine1. 添加依赖Maven!-- Guava --dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion33.2.1-jre/version/dependency!-- Caffeine --dependencygroupIdcom.github.ben-manes.caffeine/groupIdartifactIdcaffeine/artifactIdversion3.1.8/version/dependencyGradleimplementationcom.google.guava:guava:33.2.1-jreimplementationcom.github.ben-manes.caffeine:caffeine:3.1.82. Guava Cache 示例基于 maximumSize 的 LRUimportcom.google.common.cache.Cache;importcom.google.common.cache.CacheBuilder;importjava.util.concurrent.TimeUnit;publicclassGuavaLRUExample{publicstaticvoidmain(String[]args){// 创建最大容量为 3 的缓存基于访问顺序LRUCacheString,StringcacheCacheBuilder.newBuilder().maximumSize(3)// 最多 3 个条目.expireAfterAccess(10,TimeUnit.MINUTES)// 可选10分钟未访问则过期.recordStats()// 可选开启统计.build();// 写入数据cache.put(key1,A);cache.put(key2,B);cache.put(key3,C);System.out.println(cache.asMap());// {key1A, key2B, key3C}// 访问 key1LRU 会将 key1 移到最近使用的位置cache.getIfPresent(key1);// 插入新 key4此时 size 将超过 3最久未使用的 key2 会被淘汰cache.put(key4,D);System.out.println(cache.asMap());// {key3C, key1A, key4D}// 查看统计信息System.out.println(cache.stats());// 命中率等}}关键点maximumSize(3)自动实现 LRU基于访问顺序。getIfPresent不会自动加载若需要自动加载可以用LoadingCache并实现load方法。淘汰策略是异步执行的最终一致。3. Caffeine 示例更现代性能更好importcom.github.benmanes.caffeine.cache.Cache;importcom.github.benmanes.caffeine.cache.Caffeine;importjava.util.concurrent.TimeUnit;publicclassCaffeineLRUExample{publicstaticvoidmain(String[]args){// 创建最大容量为 3 的缓存基于访问顺序LRU 是其 W-TinyLFU 的一部分CacheString,StringcacheCaffeine.newBuilder().maximumSize(3).expireAfterAccess(10,TimeUnit.MINUTES)// 可选.recordStats().build();cache.put(key1,A);cache.put(key2,B);cache.put(key3,C);System.out.println(cache.asMap());// {key1A, key2B, key3C}// 访问 key1cache.getIfPresent(key1);// 插入 key4 - 淘汰最久未使用的 key2cache.put(key4,D);System.out.println(cache.asMap());// {key3C, key1A, key4D}// 统计信息System.out.println(cache.stats());}}Caffeine 特有的高级用法异步加载、手动加载等LoadingCacheKey,GraphgraphsCaffeine.newBuilder().maximumSize(10_000).expireAfterWrite(5,TimeUnit.MINUTES).build(key-createExpensiveGraph(key));4. 如何验证 LRU 行为访问顺序淘汰// 两个库行为一致cache.put(a,1);cache.put(b,2);cache.put(c,3);cache.getIfPresent(a);// 将 a 变成最近使用cache.put(d,4);// 容量超限淘汰最久未使用的 bassertcache.asMap().containsKey(b)false;assertcache.asMap().containsKey(a)true;5. 线程安全说明Guava Cache和Caffeine返回的Cache实例都是线程安全的内部使用了ConcurrentHashMap类似的并发控制无需额外同步。可以直接在多线程环境中共享使用。6. 何时用 Guava何时用 CaffeineGuava成熟稳定依赖较广适合老项目或团队已经使用 Guava。Caffeine性能更高尤其是高并发读多写少场景命中率更高W-TinyLFU 算法内存占用更低。推荐新项目使用 Caffeine。Spring 5 和 Spring Boot 2.x 已将 Caffeine 作为默认的CacheManager实现替代 Guava。