LinkedHashMap源码解析

之前分析过HashMap的源码,LinkedHashMap是继承自HashMap,将HashMap中的数据增加了一种链表结构。大部分方法是相同的,流程也一样,不同是createEntry和transfer方法,还有Entry的数据结构。Entry在之前的基础上添加了before和after。

LinkedHashMap提供特殊的构造方法来创建链接哈希映射,该哈希映射的迭代顺序就是最后访问其条目的顺序,从近期访问最少到近期访问最多的顺序(访问顺序)。这种映射很适合构建 LRU 缓存。Android中的图片缓存中经常用到。

2.成员变量

1
2
private transient Entry<K,V> header; //表示维护链表的头节点。
private final boolean accessOrder; //表示是否按照最后访问其条目的顺序重新排序。

表示任务队列。

3.方法

1
2
3
4
5
6
7
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}

在之前的基础上还维护了一种链表结构。将新添加的数据放在链表最后面

1
2
3
4
5
6
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

这个方法就是将当期元素放在列表的最后面。

1
2
3
4
5
6
7
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;
}

getEntry是HashMap中的方法,没有重写。获取元素后会重新排序链表。

1
2
3
4
5
6
7
8
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

accessOrder表示是否需要重新排序。

1
2
3
4
5
6
7
8
9
10
11
private void remove() {
before.after = after;
after.before = before;
}

private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

这两个方法就是将当期元素从当前位置移动到最后的位置。