探索LRU常用数据结构—LinkedHashMap的hash冲突问题

LRU算法是什么

LRU(Least recently used,最近最少使用)是一种缓存经常用到的算法,根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

利用LinkedHashMap实现简单的LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class UseLinkedHashMapCache<K,V> extends LinkedHashMap<K,V> {
private int cacheSize;

public UseLinkedHashMapCache(int cacheSize) {
/**
* 参数:
* initialCapacity – 初始容量
* loadFactor – 负载因子
* accessOrder – 排序模式 - 访问顺序为真,插入顺序为假
*/
super(16, 0.75f, true);
this.cacheSize = cacheSize;
}

}

问题

利用LinkedHashMap来实现LRU很简单,但是在写demo的时候我产生了一个疑惑:LinkedHashMap在产生hash冲突时如果通过链地址法来解决,那么LinkedHashMap中的双向链表的顺序是怎么样的呢?

产生疑惑,动手解决,通过上面那个demo试一下就知道了:

首先先试一下demo是否能按照我们想的正常淘汰元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
UseLinkedHashMapCache<String, Integer> mapCache = new UseLinkedHashMapCache<>(3);
mapCache.put("Aaa", 4);
mapCache.put("BB", 6);
mapCache.put("3", 2);
mapCache.put("4", 3);

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

结果是正常的:

1
2
3
value : 6
value : 2
value : 3

接下来让我们试试改动一下key,让它产生hash冲突:

1
2
3
4
mapCache.put("Aa", 4); // "Aa".hashCode()  2112
mapCache.put("BB", 6); // "BB".hashCode() 2112
mapCache.put("3", 2);
mapCache.put("4", 3);

输出结果也是一样:

1
2
3
value : 6
value : 2
value : 3

尝试多个hash冲突:

1
2
3
4
mapCache.put("Aa", 4);
mapCache.put("BB", 6);
mapCache.put("Bb", 2); // 2144
mapCache.put("CC", 3); // 2144

结果:

1
2
3
value : 6
value : 2
value : 3

经过多次测试及查看源码,LinkedHashMap就是维护了一个双向链表来保证可以按照插入顺序访问及访问顺序访问,并且在value中每个node都保存了key的值,用于在删除链表节点时可以顺便把key的值删掉。