LinkdHashSet底層怎么實現元素有序？

從源碼的角度來對LinkedHashSet尋根問底！

先一覽LinkedHashSet類中的所有方法，發現就是一些構造方法，沒什么特別的。。spliterator方法也只是個迭代器！

從構造器中的super方法點過去可得見端倪，原來構造器中的父級構造器使用的是LinkedHashMap進行實例化，那么LinkedHashSet的特性勢必跟LinkedHashMap息息相關，換句話說LinkedHashSet的輸出有序來自于LinkedHashMap；

下面對LinkedHashMap進行詳細分析：

LinkedHashMap繼承HashMap，實現了Map，很明顯LinkedHashMap也算是HashMap，還保存了數組+鏈表的結構，至于有序的原因肯定不會是因為Map接口和繼承HashMap，也就是說LinkedHashMap的有序，肯定就是在LinkedHashMap類中實現的；

HashMap的底層數據結構是使用數組中的位置作為桶，每個桶中放置一份鏈表（或者紅黑樹），而hashCode落在哪一個桶是不確定的，沒有關聯關系，所以HashMap不能做到有序輸出，而LinkedHashMap使用的是雙重鏈表形式，保存在map中的數據不僅在每一個桶里使用鏈表維護有序，還在每個值上維護鏈表來維護有序；

借用圖一張，如下：

不僅如此，LinkedHashMap的迭代方式有兩種，一種是按照插入順序排序（迭代時就像隊列一樣），一種是訪問排序（像棧一樣，后訪問的放在棧頭，可作為LRU實現）

下面分析下主要源碼：

1，先看LinkedHashMap中的內部類Entry：

Entry繼承于HashMap.Node，Node對象中有hash，key，value等一個key-value結構，還有next作為hashMap中同一個桶下面的entry指向，LinkedHashMap.Entry新獲得了這些屬性，且新定義了兩個屬性Entry before, after，用來對所有的entry維護一個指向，變成一個雙向鏈表；

其余的諸如LinkedKeyIterator，LinkedEntrySet等內部類都是作為迭代器，

2，再看LinkedHashMap中的屬性：

LinkedHashMap中的主要屬性有是三個head，tail（維護鏈表的頭尾，很容易理解），accessOrder：注釋寫的很清楚，就是true的時候就是訪問順序，false的時候是插入順序；

3，LinkedHashMap中的方法： ①，put方法：LinkedHashMap中溜了一圈，并沒發現有put方法，難道是使用的HashMap的put方法？那entry的鏈表是怎么做到的呢？

從HashMap中的put方法可以看到，計算了hash值之后就調用了putVal方法，而在生成新插入的元素的時候，使用的是newNode方法，LinkedHashMap確實沒有重寫put方法，但是重寫了newNode方法，從代碼中可以看到HashMap中的newNode方法，只是單純的new了一個Node返回，而LinkedHashMap中的newNode方法不僅new了對象，還調用linkNodeLast，將對象掛在了鏈表的tail節點上，形成鏈表；（by the way，由此可見jdk中數據結構對于多態特性（重寫之后調用子類方法）使用的淋漓盡致）

跟newNode方法類似的還有一個newTreeNode方法，這個也是在HashMap中的put方法里進行調用的，也就是紅黑樹結構；

②，get方法：從get方法中可以看到，如果accessOrder為false，那么LinkedHashMap使用的get方法和HashMap一樣，計算相應的hash值，比較key值（==,equals），匹配上則返回，如果accessOrder為true，則調用afterNodeAccess方法，判斷各種情況，然后把這個值設置為tail，保證是棧頭的位置，下次最先查找到； 代碼如上截圖！

③，remove方法：

LinkedHashMap中的remove方法和HashMap中的是一樣的，但是最后的afterNodeRemoval方法在HashMap中的方法體是空的，而在LinkedHashMap中進行了重寫，把這個node的后一個節點接到了前一個節點上，這個node相當于脫鏈了。。 代碼如下截圖：

總的來說LinkedHashMap相比HashMap增加了鏈表特性，維護了元素的有序，雖然方法大部分都是用的HashMap的方法，但是使用重寫這種多態特性，在LinkedHashMap中進行了不同了實現，可以說這也是我們開發代碼時應該要學習的，以后再擴展其他類型的HashMap，只用重寫部分方法即可實現！

LinkedHashMap就說到這，筆者已經分享了很多java方面的技術，有很多幫助到了一些朋友！還會一直持續分享，敬請關注。。。