常用缓存算法——LRU

Ordiy Lv5

2017-01-01 2017-01-01 Created 2025-03-27 12:22:14 2025-03-27 12:22:14 Updated

corejava
| java
| net
| lru

LRU算法

Least recently used（LRU）一种常用的缓存算法,通过首先丢弃最近最少使用的记录。LRU算法需要跟踪何时使用了什么，并确保算法始终丢弃最近最少使用的记录。 LRU算法及其实现-以LinkedHashMap为例：

LRU 使用`LinkedHashMap`代码实现

package com.github.ordiy.map;

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 经典的LRU 算法
 *  热点数据缓存
 * @Author:ordiy
 */
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
    private int cacheSize;

    public LRUCache( int cacheSize) {
        super(cacheSize,(float)0.75,true);
        this.cacheSize = cacheSize;
    }
     @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
       // System.out.println(eldest);
        return size() > cacheSize;
    }
}

测试代码

@Test
public void testKey(){
    LRUCache<String,Integer> cache =  new LRUCache<>(5);
    //初始化数据
    for (int i = 0; i < 5; i++) {
        cache.put("key"+i,i);
    }
    // 模拟最近使用
    String key = "key3";
    cache.get(key);
    System.out.println("after get-->:"+ key);
    printMap(cache);

    //put data and remove Eldest Entry
    cache.put("key10",10);
    System.out.println("after put data and remove Eldest Entry");
    printMap(cache);
}

输出结果

after get-->:key3
cache order:
key0=0 hashCode: 3288497 , key1=1 hashCode: 3288499 , key2=2 hashCode: 3288497 , key4=4 hashCode: 3288497 , key3=3 hashCode: 3288503 ,
3288497
after put data and remove Eldest Entry
cache order:
key1=1 hashCode: 3288499 , key2=2 hashCode: 3288497 , key4=4 hashCode: 3288497 , key3=3 hashCode: 3288503 , key10=10 hashCode: 101943476 ,

过程解析

使用LinkedHashMap的记录数据顺序、accessOrder、removeEldestEntry特性实现了一个简单的LRU。在分布式场景下，需要使用类似redis,pika等软件进行实现。 注意因为LinkedHashMap并非线程安全的，多线程场景需要使用Collections.synchronizedMap进行包装 **分布式场景可以用 Redis 等组件实现 **

总结

LRU缓存有其局限性，在类似于双11这样的场景，流量/活跃用户突然大增时会出现缓存击穿问题。

参考:

https://juejin.im/post/5a4b433b6fb9a0451705916f LinkedHashMap 源码详细分 oracle doc LinkedHashMap Java集合类 LinkedHashMap

Title: 常用缓存算法——LRU
Author: Ordiy
Created at : 2017-01-01 00:00:00
Updated at : 2025-03-27 12:22:14
Link: https://ordiy.github.io/posts/2018-01-01-LRU-algorithms/
License: This work is licensed under CC BY 4.0.

On this page

常用缓存算法——LRU

LRU算法
LRU 使用LinkedHashMap代码实现
总结
参考: