LinkedHashMap实现LRU(最近最久未使用)算法

前言

缓存在项目中经常使用,而缓存是在内存中,所以相当宝贵,并且是有限的。LRU算法是将最近一次使用时间离现在时间最远的数据删除掉。熟悉操作系统的话可以知道,LRU也是作为缺页中断时淘汰页面的页面置换算法的一种实现。本次用LinkedHashMap实现LRU(最近最久使用)算法。

LinkedHashMap默认元素顺序是put()顺序,可是代参数的构造函数中可以设置为访问顺序

1
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)

  • initialCapacity 初始容量
  • loadFactor 加载因子,一般是 0.75f
  • accessOrder false 基于插入顺序 true 基于访问顺序(get一个元素后,这个元素被加到最后,使用了LRU 最近最少被使用的调度算法)

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class LRUcache<K, V> {
LinkedHashMap<K, V> cache = null;
private int cacheSize;
public LRUcache(int cacheSize){
this.cacheSize = (int) Math.ceil (cacheSize / 0.75f) + 1;
cache = new LinkedHashMap<K, V>(this.cacheSize,0.75f,true){
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
};
}

public V get(K key){
return (V) cache.get(key);
}
public V set(K key,V value){
return cache.put(key, value);
}

public int getCacheSize() {
return cacheSize;
}

public void setCacheSize(int cacheSize) {
this.cacheSize = cacheSize;
}

public void PrintlnCache(){
Set<Map.Entry<K,V>> set = cache.entrySet();
for(Map.Entry<K,V> entry : set){
K key = entry.getKey();
V value = entry.getValue();
System.out.println("key:"+key+"value:"+value);
}
System.out.println("-----------");

}


public static void main(String[] args) {
LRUcache<Integer, Integer> lruCache = new LRUcache<>(4);
lruCache.set(1, 5);
lruCache.set(2, 4);
lruCache.set(3, 3);
lruCache.set(4, 2);
lruCache.PrintlnCache();
lruCache.set(5, 1);//此时(1,5)已被淘汰
lruCache.PrintlnCache();
}

}

输出

1
2
3
4
5
6
7
8
9
10
key:1value:5
key:2value:4
key:3value:3
key:4value:2
-----------
key:2value:4
key:3value:3
key:4value:2
key:5value:1
-----------