集合框架源碼分析linkedhashmap簡介

1、LinkedHashMap簡介 LinkedHashMap是HashMap的子類，與HashMap有著同樣的存儲結(jié)構(gòu)，但它加入了一個雙向鏈表的頭結(jié)點(diǎn)，將所有put到LinkedHashmap的節(jié)點(diǎn)一一串成了一個雙向循環(huán)鏈表，因此它保留了節(jié)點(diǎn)插入的順序，可以使節(jié)點(diǎn)的輸出順序與輸入順序相同。 LinkedHashMap可以用來實(shí)現(xiàn)LRU算法（這會在下面的源碼中進(jìn)行分析）。 LinkedHashMap同樣是非線程安全的，只在單線程環(huán)境下使用。 LinkedHashMap源碼剖析 LinkedHashMap源碼如下（加入了詳細(xì)的注釋）：java HYPERLINK /ns_code/article/d

2、etails/37867985 o view plain view plain HYPERLINK /ns_code/article/details/37867985 o copy copypackagejava.util;importjava.io.*;publicclassLinkedHashMapextendsHashMapimplementsMapprivatestaticfinallongserialVersionUID=3801124242820219131L;/雙向循環(huán)鏈表的頭結(jié)點(diǎn)，整個LinkedHa只喲shMap中只有一個header，/它將哈希表中所有的Entry貫穿起來，

3、header中不保存key-value對，只保存前后節(jié)點(diǎn)的引用privatetransientEntryheader;/雙向鏈表中元素排序規(guī)則的標(biāo)志位。/accessOrder為false，表示按插入順序排序/accessOrder為true，表示按訪問順序排序privatefinalbooleanaccessOrder;/調(diào)用HashMap的構(gòu)造方法來構(gòu)造底層的數(shù)組publicLinkedHashMap(intinitialCapacity,floatloadFactor)super(initialCapacity,loadFactor);accessOrder=false;/鏈表中的元素默

4、認(rèn)按照插入順序排序/加載因子取默認(rèn)的0.75fpublicLinkedHashMap(intinitialCapacity)super(initialCapacity);accessOrder=false;/加載因子取默認(rèn)的0.75f，容量取默認(rèn)的16publicLinkedHashMap()super();accessOrder=false;/含有子Map的構(gòu)造方法，同樣調(diào)用HashMap的對應(yīng)的構(gòu)造方法publicLinkedHashMap(Mapm)super(m);accessOrder=false;/該構(gòu)造方法可以指定鏈表中的元素排序的規(guī)則publicLinkedHashMap(in

5、tinitialCapacity,floatloadFactor,booleanaccessOrder)super(initialCapacity,loadFactor);this.accessOrder=accessOrder;/覆寫父類的init()方法（HashMap中的init方法為空），/該方法在父類的構(gòu)造方法和Clone、readObject中在插入元素前被調(diào)用，/初始化一個空的雙向循環(huán)鏈表，頭結(jié)點(diǎn)中不保存數(shù)據(jù)，頭結(jié)點(diǎn)的下一個節(jié)點(diǎn)才開始保存數(shù)據(jù)。voidinit()header=newEntry(-1,null,null,null);header.before=header.aft

6、er=header;/覆寫HashMap中的transfer方法，它在父類的resize方法中被調(diào)用，/擴(kuò)容后，將key-value對重新映射到新的newTable中/覆寫該方法的目的是為了提高復(fù)制的效率，/這里充分利用雙向循環(huán)鏈表的特點(diǎn)進(jìn)行迭代，不用對底層的數(shù)組進(jìn)行for循環(huán)。voidtransfer(HashMap.EntrynewTable)intnewCapacity=newTable.length;for(Entrye=header.after;e!=header;e=e.after)intindex=indexFor(e.hash,newCapacity);e.next=newTa

7、bleindex;newTableindex=e;/覆寫HashMap中的containsValue方法，/覆寫該方法的目的同樣是為了提高查詢的效率，/利用雙向循環(huán)鏈表的特點(diǎn)進(jìn)行查詢，少了對數(shù)組的外層for循環(huán)publicbooleancontainsValue(Objectvalue)/Overriddentotakeadvantageoffasteriteratorif(value=null)for(Entrye=header.after;e!=header;e=e.after)if(e.value=null)returntrue;elsefor(Entrye=header.after;e

8、!=header;e=e.after)if(value.equals(e.value)returntrue;returnfalse;/覆寫HashMap中的get方法，通過getEntry方法獲取Entry對象。/注意這里的recordAccess方法，/如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做，/如果鏈表中元素的排序規(guī)則是按照訪問的先后順序排序的話，則將e移到鏈表的末尾處。publicVget(Objectkey)Entrye=(Entry)getEntry(key);if(e=null)returnnull;e.recordAccess(this);retur

9、ne.value;/清空HashMap，并將雙向鏈表還原為只有頭結(jié)點(diǎn)的空鏈表publicvoidclear()super.clear();header.before=header.after=header;/Enty的數(shù)據(jù)結(jié)構(gòu)，多了兩個指向前后節(jié)點(diǎn)的引用privatestaticclassEntryextendsHashMap.Entry/Thesefieldscomprisethedoublylinkedlistusedforiteration.Entrybefore,after;/調(diào)用父類的構(gòu)造方法Entry(inthash,Kkey,Vvalue,HashMap.Entrynext)su

10、per(hash,key,value,next);/雙向循環(huán)鏈表中，刪除當(dāng)前的Entryprivatevoidremove()before.after=after;after.before=before;/雙向循環(huán)立鏈表中，將當(dāng)前的Entry插入到existingEntry的前面privatevoidaddBefore(EntryexistingEntry)after=existingEntry;before=existingEntry.before;before.after=this;after.before=this;/覆寫HashMap中的recordAccess方法（HashMap中該

11、方法為空），/當(dāng)調(diào)用父類的put方法，在發(fā)現(xiàn)插入的key已經(jīng)存在時，會調(diào)用該方法，/調(diào)用LinkedHashmap覆寫的get方法時，也會調(diào)用到該方法，/該方法提供了LRU算法的實(shí)現(xiàn)，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部，/accessOrder為true時，get方法會調(diào)用recordAccess方法/put方法在覆蓋key-value對時也會調(diào)用recordAccess方法/它們導(dǎo)致Entry最近使用，因此將其移到雙向鏈表的末尾voidrecordAccess(HashMapm)LinkedHashMaplm=(LinkedHashMap)m;/如果鏈表中元素按照訪問順序排序，則

12、將當(dāng)前訪問的Entry移到雙向循環(huán)鏈表的尾部，/如果是按照插入的先后順序排序，則不做任何事情。if(lm.accessOrder)lm.modCount+;/移除當(dāng)前訪問的Entryremove();/將當(dāng)前訪問的Entry插入到鏈表的尾部addBefore(lm.header);voidrecordRemoval(HashMapm)remove();/迭代器privateabstractclassLinkedHashIteratorimplementsIteratorEntrynextEntry=header.after;EntrylastReturned=null;/*ThemodCoun

13、tvaluethattheiteratorbelievesthatthebacking*Listshouldhave.Ifthisexpectationisviolated,theiterator*hasdetectedconcurrentmodification.*/intexpectedModCount=modCount;publicbooleanhasNext()returnnextEntry!=header;publicvoidremove()if(lastReturned=null)thrownewIllegalStateException();if(modCount!=expect

14、edModCount)thrownewConcurrentModificationException();LinkedHashMap.this.remove(lastReturned.key);lastReturned=null;expectedModCount=modCount;/從head的下一個節(jié)點(diǎn)開始迭代EntrynextEntry()if(modCount!=expectedModCount)thrownewConcurrentModificationException();if(nextEntry=header)thrownewNoSuchElementException();En

15、trye=lastReturned=nextEntry;nextEntry=e.after;returne;/key迭代器privateclassKeyIteratorextendsLinkedHashIteratorpublicKnext()returnnextEntry().getKey();/value迭代器privateclassValueIteratorextendsLinkedHashIteratorpublicVnext()returnnextEntry().value;/Entry迭代器privateclassEntryIteratorextendsLinkedHashIter

16、atorMap.EntrypublicMap.Entrynext()returnnextEntry();/TheseOverridesalterthebehaviorofsuperclassviewiterator()methodsIteratornewKeyIterator()returnnewKeyIterator();IteratornewValueIterator()returnnewValueIterator();IteratorMap.EntrynewEntryIterator()returnnewEntryIterator();/覆寫HashMap中的addEntry方法，Lin

17、kedHashmap并沒有覆寫HashMap中的put方法，/而是覆寫了put方法所調(diào)用的addEntry方法和recordAccess方法，/put方法在插入的key已存在的情況下，會調(diào)用recordAccess方法，/在插入的key不存在的情況下，要調(diào)用addEntry插入新的EntryvoidaddEntry(inthash,Kkey,Vvalue,intbucketIndex)/創(chuàng)建新的Entry，并插入到LinkedHashMap中createEntry(hash,key,value,bucketIndex);/雙向鏈表的第一個有效節(jié)點(diǎn)（header后的那個節(jié)點(diǎn)）為近期最少使用的節(jié)點(diǎn)

18、Entryeldest=header.after;/如果有必要，則刪除掉該近期最少使用的節(jié)點(diǎn)，/這要看對removeEldestEntry的覆寫,由于默認(rèn)為false，因此默認(rèn)是不做任何處理的。if(removeEldestEntry(eldest)removeEntryForKey(eldest.key);else/擴(kuò)容到原來的2倍if(size=threshold)resize(2*table.length);voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex)/創(chuàng)建新的Entry，并將其插入到數(shù)組對應(yīng)槽的單鏈表的頭結(jié)點(diǎn)處，這點(diǎn)與HashM

19、ap中相同HashMap.Entryold=tablebucketIndex;Entrye=newEntry(hash,key,value,old);tablebucketIndex=e;/每次插入Entry時，都將其移到雙向鏈表的尾部，/這便會按照Entry插入LinkedHashMap的先后順序來迭代元素，/同時，新put進(jìn)來的Entry是最近訪問的Entry，把其放在鏈表末尾，符合LRU算法的實(shí)現(xiàn)e.addBefore(header);size+;/該方法是用來被覆寫的，一般如果用LinkedHashmap實(shí)現(xiàn)LRU算法，就要覆寫該方法，/比如可以將該方法覆寫為如果設(shè)定的內(nèi)存已滿，則返回

20、true，這樣當(dāng)再次向LinkedHashMap中put/Entry時，在調(diào)用的addEntry方法中便會將近期最少使用的節(jié)點(diǎn)刪除掉（header后的那個節(jié)點(diǎn)）。protectedbooleanremoveEldestEntry(Map.Entryeldest)returnfalse; 幾點(diǎn)總結(jié) 關(guān)于LinkedHashMap的源碼，給出以下幾點(diǎn)比較重要的總結(jié)： 1、從源碼中可以看出，LinkedHashMap中加入了一個head頭結(jié)點(diǎn)，將所有插入到該LinkedHashMap中的Entry按照插入的先后順序依次加入到以head為頭結(jié)點(diǎn)的雙向循環(huán)鏈表的尾部。 實(shí)際上就是HashMap和Link

21、edList兩個集合類的存儲結(jié)構(gòu)的結(jié)合。在LinkedHashMapMap中，所有put進(jìn)來的Entry都保存在如第一個圖所示的哈希表中，但它又額外定義了一個以head為頭結(jié)點(diǎn)的空的雙向循環(huán)鏈表，每次put進(jìn)來Entry，除了將其保存到對哈希表中對應(yīng)的位置上外，還要將其插入到雙向循環(huán)鏈表的尾部。 2、LinkedHashMap由于繼承自HashMap，因此它具有HashMap的所有特性，同樣允許key和value為null。 3、注意源碼中的accessOrder標(biāo)志位，當(dāng)它false時，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序，即每次put到Link

22、edHashMap中的Entry都放在雙向鏈表的尾部，這樣遍歷雙向鏈表時，Entry的輸出順序便和插入的順序一致，這也是默認(rèn)的雙向鏈表的存儲順序；當(dāng)它為true時，表示雙向鏈表中的元素按照訪問的先后順序排列，可以看到，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有調(diào)用recordAccess方法（put方法在key相同，覆蓋原有的Entry的情況下調(diào)用recordAccess方法），該方法判斷accessOrder是否為true，如果是，則將當(dāng)前訪問的Entry（put進(jìn)來的Entry或get出來的Entry）移到雙向鏈表的尾部（k

23、ey不相同時，put新Entry時，會調(diào)用addEntry，它會調(diào)用creatEntry，該方法同樣將新插入的元素放入到雙向鏈表的尾部，既符合插入的先后順序，又符合訪問的先后順序，因?yàn)檫@時該Entry也被訪問了），否則，什么也不做。 4、注意構(gòu)造方法，前四個構(gòu)造方法都將accessOrder設(shè)為false，說明默認(rèn)是按照插入順序排序的，而第五個構(gòu)造方法可以自定義傳入的accessOrder的值，因此可以指定雙向循環(huán)鏈表中元素的排序規(guī)則，一般要用LinkedHashMap實(shí)現(xiàn)LRU算法，就要用該構(gòu)造方法，將accessOrder置為true。 5、LinkedHashMap并沒有覆寫HashMa

24、p中的put方法，而是覆寫了put方法中調(diào)用的addEntry方法和recordAccess方法，我們回過頭來再看下HashMap的put方法：java HYPERLINK /ns_code/article/details/37867985 o view plain view plain HYPERLINK /ns_code/article/details/37867985 o copy copy/將“key-value”添加到HashMap中publicVput(Kkey,Vvalue)/若“key為null”，則將該鍵值對添加到table0中。if(key=null)returnputFo

25、rNullKey(value);/若“key不為null”，則計算該key的哈希值，然后將其添加到該哈希值對應(yīng)的鏈表中。inthash=hash(key.hashCode();inti=indexFor(hash,table.length);for(Entrye=tablei;e!=null;e=e.next)Objectk;/若“該key”對應(yīng)的鍵值對已經(jīng)存在，則用新的value取代舊的value。然后退出！if(e.hash=hash&(k=e.key)=key|key.equals(k)VoldValue=e.value;e.value=value;e.recordAccess(this

26、);returnoldValue;/若“該key”對應(yīng)的鍵值對不存在，則將“key-value”添加到table中modCount+;/將key-value添加到tablei處addEntry(hash,key,value,i);returnnull; 當(dāng)要put進(jìn)來的Entry的key在哈希表中已經(jīng)在存在時，會調(diào)用recordAccess方法，當(dāng)該key不存在時，則會調(diào)用addEntry方法將新的Entry插入到對應(yīng)槽的單鏈表的頭部。 我們先來看recordAccess方法：java HYPERLINK /ns_code/article/details/37867985 o view pla

27、in view plain HYPERLINK /ns_code/article/details/37867985 o copy copy/覆寫HashMap中的recordAccess方法（HashMap中該方法為空），/當(dāng)調(diào)用父類的put方法，在發(fā)現(xiàn)插入的key已經(jīng)存在時，會調(diào)用該方法，/調(diào)用LinkedHashmap覆寫的get方法時，也會調(diào)用到該方法，/該方法提供了LRU算法的實(shí)現(xiàn)，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部，/accessOrder為true時，get方法會調(diào)用recordAccess方法/put方法在覆蓋key-value對時也會調(diào)用recordAccess方法

28、/它們導(dǎo)致Entry最近使用，因此將其移到雙向鏈表的末尾voidrecordAccess(HashMapm)LinkedHashMaplm=(LinkedHashMap)m;/如果鏈表中元素按照訪問順序排序，則將當(dāng)前訪問的Entry移到雙向循環(huán)鏈表的尾部，/如果是按照插入的先后順序排序，則不做任何事情。if(lm.accessOrder)lm.modCount+;/移除當(dāng)前訪問的Entryremove();/將當(dāng)前訪問的Entry插入到鏈表的尾部addBefore(lm.header); 該方法會判斷accessOrder是否為true，如果為true，它會將當(dāng)前訪問的Entry（在這里指pu

29、t進(jìn)來的Entry）移動到雙向循環(huán)鏈表的尾部，從而實(shí)現(xiàn)雙向鏈表中的元素按照訪問順序來排序（最近訪問的Entry放到鏈表的最后，這樣多次下來，前面就是最近沒有被訪問的元素，在實(shí)現(xiàn)、LRU算法時，當(dāng)雙向鏈表中的節(jié)點(diǎn)數(shù)達(dá)到最大值時，將前面的元素刪去即可，因?yàn)榍懊娴脑厥亲罱钌偈褂玫模?，否則什么也不做。 再來看addEntry方法：java HYPERLINK /ns_code/article/details/37867985 o view plain view plain HYPERLINK /ns_code/article/details/37867985 o copy copy/覆寫HashM

30、ap中的addEntry方法，LinkedHashmap并沒有覆寫HashMap中的put方法，/而是覆寫了put方法所調(diào)用的addEntry方法和recordAccess方法，/put方法在插入的key已存在的情況下，會調(diào)用recordAccess方法，/在插入的key不存在的情況下，要調(diào)用addEntry插入新的EntryvoidaddEntry(inthash,Kkey,Vvalue,intbucketIndex)/創(chuàng)建新的Entry，并插入到LinkedHashMap中createEntry(hash,key,value,bucketIndex);/雙向鏈表的第一個有效節(jié)點(diǎn)（heade

31、r后的那個節(jié)點(diǎn)）為近期最少使用的節(jié)點(diǎn)Entryeldest=header.after;/如果有必要，則刪除掉該近期最少使用的節(jié)點(diǎn)，/這要看對removeEldestEntry的覆寫,由于默認(rèn)為false，因此默認(rèn)是不做任何處理的。if(removeEldestEntry(eldest)removeEntryForKey(eldest.key);else/擴(kuò)容到原來的2倍if(size=threshold)resize(2*table.length);voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex)/創(chuàng)建新的Entry，并將其插入到數(shù)組對應(yīng)槽

32、的單鏈表的頭結(jié)點(diǎn)處，這點(diǎn)與HashMap中相同HashMap.Entryold=tablebucketIndex;Entrye=newEntry(hash,key,value,old);tablebucketIndex=e;/每次插入Entry時，都將其移到雙向鏈表的尾部，/這便會按照Entry插入LinkedHashMap的先后順序來迭代元素，/同時，新put進(jìn)來的Entry是最近訪問的Entry，把其放在鏈表末尾，符合LRU算法的實(shí)現(xiàn)e.addBefore(header);size+; 同樣是將新的Entry插入到table中對應(yīng)槽所對應(yīng)單鏈表的頭結(jié)點(diǎn)中，但可以看出，在createEntr

33、y中，同樣把新put進(jìn)來的Entry插入到了雙向鏈表的尾部，從插入順序的層面來說，新的Entry插入到雙向鏈表的尾部，可以實(shí)現(xiàn)按照插入的先后順序來迭代Entry，而從訪問順序的層面來說，新put進(jìn)來的Entry又是最近訪問的Entry，也應(yīng)該將其放在雙向鏈表的尾部。 上面還有個removeEldestEntry方法，該方法如下：java HYPERLINK /ns_code/article/details/37867985 o view plain view plain HYPERLINK /ns_code/article/details/37867985 o copy copy/該方法是用來被覆寫的，一般如果用LinkedHashmap實(shí)現(xiàn)LRU算法，就要覆寫該方法，/比如可以將該方法覆寫為如果設(shè)定的內(nèi)存已滿，則返回true，這樣當(dāng)再次向LinkedHashMap中put/Entry時，在調(diào)用的addEntr