用LinkedHashMap实现LRU

什么是LRU?

如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。所以,当指定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

实现

1.数据额结构中要满足新增的在尾部和最新访问的要移动到尾部。

2.容量满了之后要删除掉最久未使用那个元素。

新建一个类继承自LinkedHashMap并重写removeEldestEntry()方法当容量不够就会淘汰 oldest 的页面。accessOrder为true时表示当前数据的插入读取顺序为访问顺序,false表示当前数据的插入读取顺序为插入顺序。

1
2
3
4
5
6
7
8
9
10
11
12
public class LruTest<K,V> extends LinkedHashMap {
protected Integer maxElements;
public LruTest(int maxSize) {
super(maxSize,1.6f,true);//accessOrder:true
maxElements = maxSize;
}

@Override
protected boolean removeEldestEntry(java.util.Map.Entry oldest){
return size()>maxElements;
}
}

测试

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
public static void main(String[] args) {
Map<String,Object> lru = new LruTest<>(5);
lru.put("key_1","value_1111");
lru.put("key_2","value_2222");
lru.put("key_3","value_3333");
lru.put("key_4","value_4444");
lru.put("key_5","value_5555");

Iterator <Map.Entry<String, Object>> it = lru.entrySet().iterator();
while(it.hasNext()){
Map.Entry<String, Object> entry = it.next();
System.out.println("key:" +entry.getKey()+ " value:" +entry.getValue());
}

System.out.println("------------------------------------------------------");
lru.get("key_2");
Iterator <Map.Entry<String, Object>> it1 = lru.entrySet().iterator();
while(it1.hasNext()){
Map.Entry<String, Object> entry = it1.next();
System.out.println("key:" +entry.getKey()+ " value:" +entry.getValue());
}

System.out.println("------------------------------------------------------");
lru.put("key_6","value_6666");
Iterator <Map.Entry<String, Object>> it2 = lru.entrySet().iterator();
while(it2.hasNext()){
Map.Entry<String, Object> entry = it2.next();
System.out.println("key:" +entry.getKey()+ " value:" +entry.getValue());
}
}

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
key:key_1 value:value_1111
key:key_2 value:value_2222
key:key_3 value:value_3333
key:key_4 value:value_4444
key:key_5 value:value_5555
------------------------------------------------------
key:key_1 value:value_1111
key:key_3 value:value_3333
key:key_4 value:value_4444
key:key_5 value:value_5555
key:key_2 value:value_2222
------------------------------------------------------
key:key_3 value:value_3333
key:key_4 value:value_4444
key:key_5 value:value_5555
key:key_2 value:value_2222
key:key_6 value:value_6666
查看评论