一、什么是 LRU
LRU(Least Recently Used,最近最少使用)是一种缓存算法,其核心思想是将最近最少使用的缓存项移除,以便为更常用的缓存项腾出空间。
在实际应用中,LRU 算法被广泛用于缓存和页面置换。
二、Java 实现 LRU 缓存算法
在 Java 中,可以使用 LinkedHashMap 来实现 LRU 缓存算法。
LinkedHashMap 是 HashMap 的一个子类,其内部使用双向链表维护元素的顺序。
具体实现思路如下:
- 继承 LinkedHashMap,重写 removeEldestEntry 方法,该方法返回 true 表示需要移除最老的缓存项;
- 在构造方法中指定 accessOrder 为 true,这样在访问元素时就会把该元素移动到链表尾部,方便后续查找和移除;
- 在访问缓存项时,使用 get 方法获取元素,并通过 removeEldestEntry 方法来判断是否需要移除最老的缓存项;
- 在添加缓存项时,使用 put 方法将元素加入 LinkedHashMap 中。
使用 LinkedHashMap 实现 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) { 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> cache = new LRUCache<>(3); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); System.out.println(cache); // {1=one, 2=two, 3=three} cache.get(2); System.out.println(cache); // {1=one, 3=three, 2=two} cache.put(4, "four"); System.out.println(cache); // {3=three, 2=two, 4=four} } }
在上面的示例代码中,我们创建了一个 LRUCache 类,继承了 LinkedHashMap,并在构造方法中指定了 accessOrder 为 true。
在 removeEldestEntry 方法中,当缓存项数量超过容量时返回 true,表示需要移除最老的缓存项。
在访问缓存项时,使用 get 方法获取元素,如果缓存项数量超过容量,则会移除最老的缓存项。
在添加缓存项时,使用 put 方法将元素加入 LinkedHashMap 中。
最后,在 main 方法中对缓存进行测试。
需要注意的是,在使用 LinkedHashMap 实现 LRU 缓存时,必须指定 accessOrder 为 true,否则 LinkedHashMap 会按照插入顺序维护元素的顺序,而不是访问顺序。
原文地址:https://blog.csdn.net/aikudexiaohai/article/details/130554371
版权声明:除特别声明外,本站所有文章皆是本站原创,转载请以超链接形式注明出处!