從Java API知道，LinkedHashMap繼承于HashMap，并且通過雙向鏈表保存各節(jié)點的位置信息，實現了順序存儲。但是如果讓你自己寫一個順序存儲的HashMap，將如何下手呢？從研究LinkedHashMap的源碼開始入手，究竟它比HashMap多了哪些東西，讓它擁有了順序存儲的能力。

1. 放入元素（put）

從放入一個元素開始，即最常見的V put(K key, V value)方法入手，LinkedHashMap并沒有重寫HashMap的put方法，但是它重寫了最關鍵的Node<K, V> newNode(int hash, K key, V value, Node next)方法，該方法首先創(chuàng)建一個HashMap.Node的子類LinkedHashMap.Entry，它比Node多了兩個指針Entry<K, V> before, after;//用于保存前后兩個節(jié)點的信息：

LinkedHashMap.Entry<K, V>內部類

其次，把要放入的元素插入雙向鏈表的表尾：

增加元素到雙向鏈表的末尾

注意：LinkedHashMap擁有兩個瞬時的屬性transient LinkedHashMap.Entry<K,V> tail;//用于保存上一個元素，即表尾；transient LinkedHashMap.Entry<K, V> head;//用于保存第一個元素，即表頭。

2. 遍歷元素（entrySet）

LinkedHashMap重寫了Map接口的Set<Map.Entry<K, V> entrySet()方法，并返回自己的內部類class LinkedEntrySet extends AbstractSet<Map.Entry<K, V>>對象。它使用LinkedEntryIterator迭代器進行遍歷，它繼承于自己的abstract class LinkedHashIterator抽象類。該迭代器擁有兩個Entry的指針next和current，并結合Entry中的before和after指針，實現了LinkedHashMap中元素的順序遍歷。

下面可以看下LinkedHashIterator的nextNode方法的實現：

LinkedHashIterator的nextNode方法

正是nextNode方法使用了LinkedHashMap.Entry<K, V>的after屬性，使得iterator的遍歷按照放入順序進行的。

3. 獲取元素（get）

LinkedHashMap重寫了Map接口的V get(Object key)方法，該方法分兩個步驟：1. 調用父類HashMap的getNode(hash(key), key)方法，獲取value；2. 如果accessOrder為true（默認為false），那么移動所訪問的元素到表尾，并修改head和tail的值：

訪問后重排序（accessOrder）