Java LRU 缓存算法详解
LRU(Least Recently Used,最近最少使用)缓存算法是一种常用的缓存淘汰策略,主要用于管理缓存中的数据。当缓存达到其容量限制时,LRU算法会移除最久未被使用的数据,以便为新数据腾出空间。
LRU 算法的核心思想是:如果一个数据在最近被访问过,那么它在将来被访问的概率也会更高。因此,LRU 会优先保留最近被访问的数据,淘汰那些长时间未被访问的数据。
在 Java 中,可以使用 LinkedHashMap
来实现 LRU 缓存。LinkedHashMap
是一个有序的 Map,它维护了元素的插入顺序或访问顺序。通过重写 removeEldestEntry
方法,可以轻松实现 LRU 缓存。
以下是一个简单的 LRU 缓存实现示例:
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// true表示按照访问顺序排序,false表示按照插入顺序排序
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LRUCache<Integer, String> lruCache = new LRUCache<>(3);
lruCache.put(1, "A");
lruCache.put(2, "B");
lruCache.put(3, "C");
System.out.println(lruCache); // {1=A, 2=B, 3=C}
lruCache.get(1); // 访问 1
lruCache.put(4, "D"); // 添加新元素,应该移除 2
System.out.println(lruCache); // {3=C, 1=A, 4=D}
}
}
构造函数:LRUCache(int capacity)
初始化缓存的容量,并调用 super
构造函数,设置 accessOrder
为 true
,以便按照访问顺序维护元素的顺序。
removeEldestEntry:重写此方法以定义何时移除最老的条目。当缓存的大小超过设定的容量时,返回 true
,表示需要移除最老的条目。
主方法:在 main
方法中,创建一个容量为 3 的 LRU 缓存,插入一些元素并进行访问。可以看到,当插入新元素时,最久未使用的元素会被移除。
优点:
LinkedHashMap
。缺点:
LinkedHashMap
的性能可能会受到影响。LRU 缓存是一种有效的缓存管理策略,适用于多种场景。通过 Java 的 LinkedHashMap
,可以方便地实现 LRU 缓存,满足基本的缓存需求。