LinkedHashMap源码解析

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

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

2.成员变量

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

表示任务队列。

3.方法

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++;
}

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

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

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

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中的方法，没有重写。获取元素后会重新排序链表。

void recordAccess(HashMap<K,V> m) {
	LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
	if (lm.accessOrder) {
		lm.modCount++;
		remove();
		addBefore(lm.header);
	}
}

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

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;
}

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