LinkedHashMap 源码分析

Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）或者是从近期访问最少到近期访问最多的顺序（访问顺序）。

LinkedHashMap性能很可能比 HashMap 稍逊一筹，不过这一点例外：LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量 成比例。

LinkedHashMap不是线程安全的。在按插入顺序链接的哈希映射中，仅更改与映射中已包含键关联的值不是结构修改。在按访问顺序链接的哈希映射中，仅利用 get 查询映射是结构修改。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
	// 头节点，不包含实际数据，做定位用。
	private transient Entry<K,V> header;

	// 迭代排序方式：true - 访问顺序, false - 插入顺序
	private final boolean accessOrder;

	// 构造一个带指定初始容量和加载因子的空插入顺序 LinkedHashMap 实例。
	public LinkedHashMap(int initialCapacity, float loadFactor) {
		super(initialCapacity, loadFactor);
		accessOrder = false;
	}

	// 构造一个带指定初始容量和默认加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
	public LinkedHashMap(int initialCapacity) {
		super(initialCapacity);
		accessOrder = false;
	}

	// 构造一个带默认初始容量 (16) 和加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
	public LinkedHashMap() {
		super();
		accessOrder = false;
	}

	// 构造一个映射关系与指定映射相同的插入顺序 LinkedHashMap 实例。所创建的 LinkedHashMap 实例具有默认的加载因子 (0.75) 和足以容纳指定映射中映射关系的初始容量。
	public LinkedHashMap(Map<? extends K, ? extends V> m) {
		super(m);
		accessOrder = false;
	}

	// 构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
	public LinkedHashMap(int initialCapacity,
			 float loadFactor,
                         boolean accessOrder) {
		super(initialCapacity, loadFactor);
		this.accessOrder = accessOrder;
	}

	// 实例化时由父类调用该方法，初始化header，前后节点指向自己。
	void init() {
		header = new Entry<K,V>(-1, null, null, null);
		header.before = header.after = header;
	}

	// 把所有的键值对迁移到新的数组中。该方法由父类的resize方法调用。重写该方法以提升性能，使用双向链表迭代会快些。
	void transfer(HashMap.Entry[] newTable) {
		int newCapacity = newTable.length;
		for (Entry<K,V> e = header.after; e != header; e = e.after) {
			int index = indexFor(e.hash, newCapacity);
			e.next = newTable[index];
			newTable[index] = e;
		}
	}

	// 如果此映射将一个或多个键映射到指定值，则返回 true。
	public boolean containsValue(Object value) {
		// Overridden to take advantage of faster iterator
		if (value==null) {
			for (Entry e = header.after; e != header; e = e.after)
				if (e.value==null)
					return true;
		} else {
			for (Entry e = header.after; e != header; e = e.after)
				if (value.equals(e.value))
					return true;
		}
		return false;
	}

	// 返回此映射到指定键的值。如果此映射中没有该键的映射关系，则返回 null 。
	// 更确切地讲，如果此映射包含满足 (key==null ? k==null : key.equals(k)) 的从键 k 到值 v 的映射关系，则此方法返回 v；否则，返回 null。（最多只能有一个这样的映射关系。） 

	// 返回 null 值并不 一定 表明此映射不包含该键的映射关系；也可能此映射将该键显式地映射为 null。可使用 containsKey 操作来区分这两种情况。
	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;
	}

	// 从该映射中移除所有映射关系。此调用返回后映射将为空。 
	public void clear() {
		super.clear();
		header.before = header.after = header;
	}

	// 键值对类
	private static class Entry<K,V> extends HashMap.Entry<K,V> {
		// 包含前置和后置节点的引用，构成了双向链表，用于迭代.
		Entry<K,V> before, after;

		Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
			super(hash, key, value, next);
		}

		// 从该双向链表中移除该节点
		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;
		}

		// 不管哪个节点被读取或修改，父类都会调用该方法。如果该LinkedHashMap是访问顺序的，则将节点加到末尾，否则不做任何操作。
		void recordAccess(HashMap<K,V> m) {
			LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
			if (lm.accessOrder) {
				lm.modCount++;
				remove();
				addBefore(lm.header);
			}
		}

		// 记录删除事件
		void recordRemoval(HashMap<K,V> m) {
			remove();
		}
	}

	// 迭代器抽象类
	private abstract class LinkedHashIterator<T> implements Iterator<T> {
		Entry<K,V> nextEntry    = header.after;
		Entry<K,V> lastReturned = null;

		// 期望修改次数初始化为修改次数
		int expectedModCount = modCount;

		public boolean hasNext() {
			return nextEntry != header;
		}

		public void remove() {
			if (lastReturned == null)
				throw new IllegalStateException();
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();

			LinkedHashMap.this.remove(lastReturned.key);
			lastReturned = null;
			expectedModCount = modCount;
		}

		Entry<K,V> nextEntry() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
			if (nextEntry == header)
				throw new NoSuchElementException();

			Entry<K,V> e = lastReturned = nextEntry; // 读取当前值
			nextEntry = e.after; // 读取下一个值，保存到nextEntry中
			return e;
		}
	}

	// 键迭代器
	private class KeyIterator extends LinkedHashIterator<K> {
		public K next() { return nextEntry().getKey(); }
	}

	// 值迭代器
	private class ValueIterator extends LinkedHashIterator<V> {
		public V next() { return nextEntry().value; }
	}

	// 键值对迭代器
	private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
		public Map.Entry<K,V> next() { return nextEntry(); }
	}

	Iterator<K> newKeyIterator()   { return new KeyIterator();   }
	Iterator<V> newValueIterator() { return new ValueIterator(); }
	Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

	// 添加键值对到链表的尾部并且根据情况移除最先节点
	void addEntry(int hash, K key, V value, int bucketIndex) {
		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);
		}
	}

	// 添加键值对。和addEntry类似，区别是少了移除最先节点和增大键值对数组
	void createEntry(int hash, K key, V value, int bucketIndex) {
		HashMap.Entry<K,V> old = table[bucketIndex];
		Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
		table[bucketIndex] = e;
		e.addBefore(header);
		size++;
	}

	// 是否移除最先节点。在缓存实现中有用。子类可以重写该方法。
	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
		return false;
	}
}