轉自http://uule.VEvb.com/blog/1522291

1. LinkedHashMap概述：

LinkedHashMap是HashMap的一個子類，它保留插入的順序，如果需要輸出的順序和輸入時的相同，那么就選用LinkedHashMap。

LinkedHashMap是Map接口的哈希表和鏈接列表實現，具有可預知的迭代順序。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。 LinkedHashMap實現與HashMap的不同之處在于，后者維護著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。 注意，此實現不是同步的。如果多個線程同時訪問鏈接的哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。

根據鏈表中元素的順序可以分為：按插入順序的鏈表，和按訪問順序(調用get方法)的鏈表。

默認是按插入順序排序，如果指定按訪問順序排序，那么調用get方法后，會將這次訪問的元素移至鏈表尾部，不斷訪問可以形成按訪問順序排序的鏈表。 可以重寫removeEldestEntry方法返回true值指定插入元素時移除最老的元素。

2. LinkedHashMap的實現：

對于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向鏈表來保存所有元素。其基本操作與父類HashMap相似，它通過重寫父類相關的方法，來實現自己的鏈接列表特性。下面我們來分析LinkedHashMap的源代碼：

類結構：

1. publicclassLinkedHashMap<K,V>extendsHashMap<K,V>implementsMap<K,V>

1) 成員變量：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了數組中保存的元素Entry，該Entry除了保存當前對象的引用外，還保存了其上一個元素before和下一個元素after的引用，從而在哈希表的基礎上又構成了雙向鏈接列表。看源代碼：

1. //true表示按照訪問順序迭代，false時表示按照插入順序
2. PRivatefinalbooleanaccessOrder;

1. /**
2. *雙向鏈表的表頭元素。
3. */
4. privatetransientEntry<K,V>header;
6. /**
7. *LinkedHashMap的Entry元素。
8. *繼承HashMap的Entry元素，又保存了其上一個元素before和下一個元素after的引用。
9. */
10. privatestaticclassEntry<K,V>extendsHashMap.Entry<K,V>{
11. Entry<K,V>before,after;
12. &hellip;…
13. }

HashMap.Entry:

1. staticclassEntry<K,V>implementsMap.Entry<K,V>{
2. finalKkey;
3. Vvalue;
4. Entry<K,V>next;
5. finalinthash;
7. Entry(inth,Kk,Vv,Entry<K,V>n){
8. value=v;
9. next=n;
10. key=k;
11. hash=h;
12. }
13. }

2) 初始化：

通過源代碼可以看出，在LinkedHashMap的構造方法中，實際調用了父類HashMap的相關構造方法來構造一個底層存放的table數組。如：

1. publicLinkedHashMap(intinitialCapacity,floatloadFactor){
2. super(initialCapacity,loadFactor);
3. accessOrder=false;
4. }

HashMap中的相關構造方法：

1. publicHashMap(intinitialCapacity,floatloadFactor){
2. if(initialCapacity<0)
3. thrownewIllegalArgumentException("Illegalinitialcapacity:"+
4. initialCapacity);
5. if(initialCapacity>MAXIMUM_CAPACITY)
6. initialCapacity=MAXIMUM_CAPACITY;
7. if(loadFactor<=0||Float.isNaN(loadFactor))
8. thrownewIllegalArgumentException("Illegalloadfactor:"+
9. loadFactor);
11. //Findapowerof2>=initialCapacity
12. intcapacity=1;
13. while(capacity<initialCapacity)
14. capacity<<=1;
16. this.loadFactor=loadFactor;
17. threshold=(int)(capacity*loadFactor);
18. table=newEntry[capacity];
19. init();
20. }

我們已經知道LinkedHashMap的Entry元素繼承HashMap的Entry，提供了雙向鏈表的功能。在上述HashMap的構造器中，最后會調用init()方法，進行相關的初始化，這個方法在HashMap的實現中并無意義，只是提供給子類實現相關的初始化調用。 LinkedHashMap重寫了init()方法，在調用父類的構造方法完成構造后，進一步實現了對其元素Entry的初始化操作。

1. voidinit(){
2. header=newEntry<K,V>(-1,null,null,null);
3. header.before=header.after=header;
4. }

3) 存儲：

LinkedHashMap并未重寫父類HashMap的put方法，而是重寫了父類HashMap的put方法調用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的雙向鏈接列表的實現。

HashMap.put:

1. publicVput(Kkey,Vvalue){
2. if(key==null)
3. returnputForNullKey(value);
4. inthash=hash(key.hashCode());
5. inti=indexFor(hash,table.length);
6. for(Entry<K,V>e=table[i];e!=null;e=e.next){
7. Objectk;
8. if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
9. VoldValue=e.value;
10. e.value=value;
11. e.recordAccess(this);
12. returnoldValue;
13. }
14. }
16. modCount++;
17. addEntry(hash,key,value,i);
18. returnnull;
19. }

重寫方法：

1. voidrecordAccess(HashMap<K,V>m){
2. LinkedHashMap<K,V>lm=(LinkedHashMap<K,V>)m;
3. if(lm.accessOrder){
4. lm.modCount++;
5. remove();
6. addBefore(lm.header);
7. }
8. }

1. voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
2. //調用create方法，將新元素以雙向鏈表的的形式加入到映射中。
3. createEntry(hash,key,value,bucketIndex);
5. //刪除最近最少使用元素的策略定義
6. Entry<K,V>eldest=header.after;
7. if(removeEldestEntry(eldest)){
8. removeEntryForKey(eldest.key);
9. }else{
10. if(size>=threshold)
11. resize(2*table.length);
12. }
13. }

1. voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){
2. HashMap.Entry<K,V>old=table[bucketIndex];
3. Entry<K,V>e=newEntry<K,V>(hash,key,value,old);
4. table[bucketIndex]=e;
5. //調用元素的addBrefore方法，將元素加入到哈希、雙向鏈接列表。
6. e.addBefore(header);
7. size++;
8. }

1. privatevoidaddBefore(Entry<K,V>existingEntry){
2. after=existingEntry;
3. before=existingEntry.before;
4. before.after=this;
5. after.before=this;
6. }

4) 讀取：

LinkedHashMap重寫了父類HashMap的get方法，實際在調用父類getEntry()方法取得查找的元素后，再判斷當排序模式accessOrder為true時，記錄訪問順序，將最新訪問的元素添加到雙向鏈表的表頭，并從原來的位置刪除。由于的鏈表的增加、刪除操作是常量級的，故并不會帶來性能的損失。

HashMap.containsValue:

1. publicbooleancontainsValue(Objectvalue){
2. if(value==null)
3. returncontainsNullValue();
5. Entry[]tab=table;
6. for(inti=0;i<tab.length;i++)
7. for(Entrye=tab[i];e!=null;e=e.next)
8. if(value.equals(e.value))
9. returntrue;
10. returnfalse;
11. }

1. /*查找Map中是否包含給定的value，還是考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。
2. */
3. publicbooleancontainsValue(Objectvalue){
4. //Overriddentotakeadvantageoffasteriterator
5. if(value==null){
6. for(Entrye=header.after;e!=header;e=e.after)
7. if(e.value==null)
8. returntrue;
9. }else{
10. for(Entrye=header.after;e!=header;e=e.after)
11. if(value.equals(e.value))
12. returntrue;
13. }
14. returnfalse;
15. }

1. /*該transfer()是HashMap中的實現：遍歷整個表的各個桶位，然后對桶進行遍歷得到每一個Entry，重新hash到newTable中，
2. //放在這里是為了和下面LinkedHashMap重寫該法的比較，
3. voidtransfer(Entry[]newTable){
4. Entry[]src=table;
5. intnewCapacity=newTable.length;
6. for(intj=0;j<src.length;j++){
7. Entry<K,V>e=src[j];
8. if(e!=null){
9. src[j]=null;
10. do{
11. Entry<K,V>next=e.next;
12. inti=indexFor(e.hash,newCapacity);
13. e.next=newTable[i];
14. newTable[i]=e;
15. e=next;
16. }while(e!=null);
17. }
18. }
19. }
20. */
22. /**
23. *transfer()方法是其父類HashMap調用resize()的時候調用的方法，它的作用是表擴容后，把舊表中的key重新hash到新的表中。
24. *這里從寫了父類HashMap中的該方法，是因為考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。
25. */
26. voidtransfer(HashMap.Entry[]newTable){
27. intnewCapacity=newTable.length;
28. for(Entry<K,V>e=header.after;e!=header;e=e.after){
29. intindex=indexFor(e.hash,newCapacity);
30. e.next=newTable[index];
31. newTable[index]=e;
32. }
33. }

1. publicVget(Objectkey){
2. //調用父類HashMap的getEntry()方法，取得要查找的元素。
3. Entry<K,V>e=(Entry<K,V>)getEntry(key);
4. if(e==null)
5. returnnull;
6. //記錄訪問順序。
7. e.recordAccess(this);
8. returne.value;
9. }

1. voidrecordAccess(HashMap<K,V>m){
2. LinkedHashMap<K,V>lm=(LinkedHashMap<K,V>)m;
3. //如果定義了LinkedHashMap的迭代順序為訪問順序，
4. //則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭。
5. if(lm.accessOrder){
6. lm.modCount++;
7. remove();
8. addBefore(lm.header);
9. }
10. }

1. /**
2. *Removesthisentryfromthelinkedlist.
3. */
4. privatevoidremove(){
5. before.after=after;
6. after.before=before;
7. }

1. /**clear鏈表，設置header為初始狀態*/
2. publicvoidclear(){
3. super.clear();
4. header.before=header.after=header;
5. }

5) 排序模式：

LinkedHashMap定義了排序模式accessOrder，該屬性為boolean型變量，對于訪問順序，為true；對于插入順序，則為false。

1. privatefinalbooleanaccessOrder;

一般情況下，不必指定排序模式，其迭代順序即為默認為插入順序。看LinkedHashMap的構造方法，如：

1. publicLinkedHashMap(intinitialCapacity,floatloadFactor){
2. super(initialCapacity,loadFactor);
3. accessOrder=false;
4. }

這些構造方法都會默認指定排序模式為插入順序。如果你想構造一個LinkedHashMap，并打算按從近期訪問最少到近期訪問最多的順序（即訪問順序）來保存元素，那么請使用下面的構造方法構造LinkedHashMap：

1. publicLinkedHashMap(intinitialCapacity,
2. floatloadFactor,
3. booleanaccessOrder){
4. super(initialCapacity,loadFactor);
5. this.accessOrder=accessOrder;
6. }

該哈希映射的迭代順序就是最后訪問其條目的順序，這種映射很適合構建LRU緩存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。該方法可以提供在每次添加新條目時移除最舊條目的實現程序，默認返回false，這樣，此映射的行為將類似于正常映射，即永遠不能移除最舊的元素。

當有新元素加入Map的時候會調用Entry的addEntry方法，會調用removeEldestEntry方法，這里就是實現LRU元素過期機制的地方，默認的情況下removeEldestEntry方法只返回false表示元素永遠不過期。

1. /**
2. *Thisoverridealtersbehaviorofsuperclassputmethod.Itcausesnewly
3. *allocatedentrytogetinsertedattheendofthelinkedlistand
4. *removestheeldestentryifappropriate.
5. */
6. voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
7. createEntry(hash,key,value,bucketIndex);
9. //Removeeldestentryifinstructed,elsegrowcapacityifappropriate
10. Entry<K,V>eldest=header.after;
11. if(removeEldestEntry(eldest)){
12. removeEntryForKey(eldest.key);
13. }else{
14. if(size>=threshold)
15. resize(2*table.length);
16. }
17. }
19. /**
20. *ThisoverridediffersfromaddEntryinthatitdoesn'tresizethe
21. *tableorremovetheeldestentry.
22. */
23. voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){
24. HashMap.Entry<K,V>old=table[bucketIndex];
25. Entry<K,V>e=newEntry<K,V>(hash,key,value,old);
26. table[bucketIndex]=e;
27. e.addBefore(header);
28. size++;
29. }
31. protectedbooleanremoveEldestEntry(Map.Entry<K,V>eldest){
32. returnfalse;
33. }

此方法通常不以任何方式修改映射，相反允許映射在其返回值的指引下進行自我修改。如果用此映射構建LRU緩存，則非常方便，它允許映射通過刪除舊條目來減少內存損耗。

例如：重寫此方法，維持此映射只保存100個條目的穩定狀態，在每次添加新條目時刪除最舊的條目。

1. privatestaticfinalintMAX_ENTRIES=100;
2. protectedbooleanremoveEldestEntry(Map.Entryeldest){
3. returnsize()>MAX_ENTRIES;
4. }

來源：http://zhangshixi.VEvb.com/blog/673789

參考：http://hi.baidu.com/yao1111yao/blog/item/3043e2f5657191f07709d7bb.html

部分修改。

使用LinkedHashMap構建LRU的Cache

http://tomyz0223.VEvb.com/blog/1035686

基于LinkedHashMap實現LRU緩存調度算法原理及應用

http://woming66.VEvb.com/blog/1284326

其實LinkedHashMap幾乎和HashMap一樣，不同的是它定義了一個Entry<K,V> header，這個header不是放在Table里，它是額外獨立出來的。LinkedHashMap通過繼承hashMap中的Entry<K,V>,并添加兩個屬性Entry<K,V> before,after,和header結合起來組成一個雙向鏈表，來實現按插入順序或訪問順序排序。