java 实现LRU 算法
LinkedHashMap 可以通过重写 removeEldestEntry 方法实现 LRU(Least Recently Used)算法。具体实现步骤如下:
- 创建一个 LinkedHashMap 对象,并设置 accessOrder 为 true,表示按照访问顺序排序。
- 重写 removeEldestEntry 方法,当 map 中的元素个数超过指定的阈值时,删除最近最少使用的元素。
- 在使用 map 时,每次访问一个元素时,都会将该元素移到链表的末尾,表示最近使用过。
示例代码如下:
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, .75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
在使用 LRUCache 时,只需要像使用普通的 Map 一样即可,例如:
LRUCache<Integer, String> cache = new LRUCache<>(2);
cache.put(1, "a");
cache.put(2, "b");
cache.get(1);
cache.put(3, "c");
System.out.println(cache); // 输出:{1=a, 3=c}
1
2
3
4
5
6
2
3
4
5
6
在上述代码中,容量为 2,先放入 1 和 2 两个元素,然后访问 1,再放入 3,此时 2 就会被删除,输出结果为{1=a, 3=c}。
编辑 (opens new window)
上次更新: 2024/04/19, 08:52:45
- 01
- idea 热部署插件 JRebel 安装及破解,不生效问题解决04-10
- 02
- spark中代码的执行位置(Driver or Executer)12-12
- 03
- 大数据技术之 SparkStreaming12-12