JAVA集合系列——LinkedHashMap实现原理
LinkedHashMap实现原理
特点
- Map接口实现，继承于HashMap
- 允许null键和null值
- 迭代有序（插入顺序或访问顺序）
- 非线程安全
- 插入快，查询快，删除快
数据结构
LinkedHashMap继承HashMap，也是哈希表和链表的结合体，但是LinkedHashMap不只于此，LinkedHashMap还维护了所有元素的双重链表，有了这个双重链表，可以在一定程度上使得LinkedHashMap元素有序，具体是插入顺序，还是访问顺序，看具体的设置。LinkedHashMap的其他操作方式与HashMap基本一致。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
//双向链表的表头元素
private transient Entry<K,V> header;
//设置迭代顺序，ture表示访问顺序，false表示插入顺序
private final boolean accessOrder;
...
//内部Entry实现，继承HashMap的Entry
private static class Entry<K,V> extends HashMap.Entry<K,V> {
//增加了before,after用来保存前一个元素和后一个元素的引用
Entry<K,V> before, after;
...
}
...
}
初始化
LinkedHashMap调用了HashMap的初始化方法来实现底层数组的初始化，由于LinkedHashMap维护的是双重链表，所以LinkedHashMap的初始化中重写了init()方法，HashMap初始化方法中会调用init()方法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//设置初始化容量和加载因子的
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//设置初始化容量，加载因子和迭代顺序的构造函数
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//用于初始化出双重链表
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
存取实现
存储
LinkedHashMap的存储方法，调用的还是父类HashMap的put方法，只是内部的部分实现的重写，代码如下：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
34void addEntry(int hash, K key, V value, int bucketIndex) {
//创建一个新的Entry，并将它加入到table对应的index位置
//将新的Entry加入双重链表中
createEntry(hash, key, value, bucketIndex);
//获取最底部的数据，判断是否有实现淘汰，没有实现的话，就判断是否需要扩容
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//获取原来index位置的链表
HashMap.Entry<K,V> old = table[bucketIndex];
//创建一个新的Entry，并将old置于新Entry的next位置
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
//将新的链表加入到table数组
table[bucketIndex] = e;
//重新构建双重链表
e.addBefore(header);
size++;
}
//Entry中的addBefore方法，将Entry加入到双重链表中
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
获取
LinkedHashMap重写了HashMap的put方法，，内容还是调用了父类的getEntry方法，代码如下：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//获取元素值
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
//迭代顺序设置
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//是否启用了访问顺序，如果启用，删除
if (lm.accessOrder) {
lm.modCount++;
//将自己从双重链表中删除
remove();
//将自己加在链表头部
addBefore(lm.header);
}
}
//将自己从双重链表中删除
private void remove() {
before.after = after;
after.before = before;
}
用LinkedHashMap实现LRU缓存
使用LinkedHashMap可以很方便的实现LRU（最近最少使用）缓存，首先需要将LinkedHashMap的迭代顺序改为访问顺序的方式，也就是accessOrder=ture;如果要实现淘汰机制的话，就需要删除最不经常使用的那个元素，我们需要控制要缓存的容量，不能不限的扩大，还记得addEntry中的是否开启淘汰吗？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19//获取最底部的数据，判断是否有实现淘汰，没有实现的话，就判断是否需要扩容
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
/*默认是关闭的
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}*/
//如果要实现淘汰机制的话，并且控制容量的大小
private int maxSize
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > maxSize;
}
相关
LinkedHashMap本身就是HashMap的子类，很多底层实现都是来源于的HashMap，对HashMap实现机制不是很熟悉的同学可以看下HashMap实现原理。
