上一篇文章中，我們已經(jīng)介紹了一個很重要的集合類-HashMap.我們也提到了它的一個特性皇拣，就是不是按我們插入的順序來讀取元素．那么严蓖，今天我們就來介紹一個能夠按照我們插入的順序來讀取元素的HashMap的變體，LinkedHashMap．
其實LinkedHashMap和HashMap的實現(xiàn)并沒有什么差別氧急，LinkedHashMap是HashMap的一個子類．從源碼中颗胡，我們可以看到，很多方法态蒂，比如put()方法杭措，在LinkedHashMap中是看不到的．
今天我們也不具體談論LinkedHashMap的實現(xiàn)細節(jié)，只是討論一下它是如何實現(xiàn)我們能按照插入元素的順序或者讀取元素的順序的順序進行遍歷．
為了實現(xiàn)這一點钾恢，LinkedHashMap修改了HashMap.Node<K,V>的實現(xiàn)手素，如下所示:
我們可以看到鸳址，它將HashMap.Node<K,V>變成了一個雙向鏈表中的一個節(jié)點．
并且，LinkedHashMap還專門維護了這么幾個屬性:
其中泉懦，head指向這個雙向鏈表的首節(jié)點稿黍，tail指向這個雙向鏈表的尾節(jié)點．access表明這個雙向鏈表應該是以什么順序來保存元素，如果這個屬性為true,則按訪問順序來保存崩哩，如果為false巡球，則按元素的插入順序來保存．
什么意思呢?
有下面代碼:
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<String, String>();
linkedHashMap.put("1", "1");
linkedHashMap.put("2", "2");
linkedHashMap.put("3", "3");
linkedHashMap.get("2");
linkedHashMap.get("3");
linkedHashMap.get("1");
如果access為true,那么此雙向鏈表為2,3,1．如果access為false,則此雙向鏈表為1,2,3.
嗯．有了這個數(shù)據(jù)結構之后，LinkedHashMap又是如何做的呢?
首先邓嘹，它重寫了HashMap的get(Object key)方法酣栈，其實現(xiàn)如下:
我們可以看到，跟HashMap的get(Object key)相比汹押，這里多了幾行:
if(access) afterNodeAccess(e);
那afterNodeAccess(e);又是什么鬼?
afterNodeAccess(Node<K,V> e)是LinkedHashMap中新增的一個操作矿筝，它的作用是，當訪問元素時棚贾，將元素添加到雙向鏈表中．
除此之外窖维，LinkedHashMap中還添加了另外兩個方法:afterNodeRemoval(Node<K, V> e)和afterNodeInsertion(boolean evict)方法，分別用于在元素被刪除以及元素被插入后妙痹，進行處理．其定義如下:
看看上面的實現(xiàn)铸史，很簡單，對吧?
接下來我們看看如何按照元素插入的順序排序.
上面我們也說過怯伊，LinkedHashMap中琳轿，其實并沒有重寫HashMap的put(Object key, Object value)方法．那么它是如何做到的呢?
要了解這一點，我們首先需要了解HashMap中putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法的實現(xiàn)耿芹，因為put(Object key, Object value)實際上就是調用的這個方法．
注意上面重點標注的那一行．
從實現(xiàn)中我們可以看到利赋，如果插入時，table(table是HashMap中的一個屬性猩系，用于存放哈希對，詳情請參考上篇文章)中沒有發(fā)生沖突中燥，也就是這個key之前是不存在的寇甸，則newNode(...),如果發(fā)生沖突，也要newNode(...).
那么疗涉，LinkedHashMap只要重寫newNode(...)這個方法拿霉，就能實現(xiàn)按照元素插入的順序來保存到雙向鏈表中了．
實際上，LinkedHashMap也確實是這么做的．
linkNodeLast(p)的意思咱扣，顧名思義绽淘，就是將新創(chuàng)建的節(jié)點插入到雙向鏈表的末尾中去.
這就理解了LinkedHashMap是如何實現(xiàn)檢索時有序的了吧?
需要注意的是，LinkedHashMap中的這個雙向鏈表闹伪，只是用于確定順序沪铭，節(jié)點在插入時壮池，要插入到table中的哪個位置，跟它可沒有關系杀怠，還是得通過table.length & hash來計算．
既然檢索時可以有序椰憋，但是我們也沒有看見LinkedHashMap為我們提供一個get(int index)的方法，來進行有序的檢索芭馔恕．那有序檢索是如何體現(xiàn)的呢?
答案就是橙依，通過迭代器來實現(xiàn)有序檢索．
一目了然吧?
從迭代器的nextNode()方法中，我們可以看到硕旗，當modCount != expectedModCount時窗骑，會拋出ConcurrentModificationException.那么什么情況下modCount != expectedModCount以及為什么不等于呢?
當我們按照訪問的順序排序，并且在用迭代器有序訪問元素時漆枚，此時如果我們調用get(Object key)创译，就會造成modCount != expectedModCount.從上面的afterNodeAccess(Node<K, V> e)，我們可以看到末尾有一句modCount++.
當我們按照插入的順序排序浪读，并且在用迭代器有序訪問元素時昔榴，如果此時調用put(Object key, Object value),也會造成modCount != expectedModCount.從HashMap的put(Object key, Object value)方法的實現(xiàn)中我們就能看到．
那么為什么要這樣做呢?
因為如果我們在迭代過程中，雙向鏈表中增加了或者刪除了元素碘橘，導致它的結構發(fā)生了變化互订，那么我們在迭代過程中可能就會遇到一些莫名其妙的錯誤，所以痘拆，為了防止這種情況仰禽，就先在nextNode()方法中，先查看一下雙向鏈表的結構有沒有發(fā)生變化．
就是這個樣子....
