成都創(chuàng)新互聯(lián)公司是專業(yè)的靖安網(wǎng)站建設(shè)公司，靖安接單;提供網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行靖安網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

1. LinkedHashMap概述：

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

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

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

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

2. LinkedHashMap的實(shí)現(xiàn)：

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

類結(jié)構(gòu)：

1. public class LinkedHashMap extends HashMap implements Map    

 1) 成員變量：

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

1. //true表示按照訪問順序迭代，false時(shí)表示按照插入順序  

2.  private final boolean accessOrder;  

1. /** 

2.  * 雙向鏈表的表頭元素。 

3.  */  

4. private transient Entry header;  

5.   

6. /** 

7.  * LinkedHashMap的Entry元素。 

8.  * 繼承HashMap的Entry元素，又保存了其上一個(gè)元素before和下一個(gè)元素after的引用。 

9.  */  

10. private static class Entry extends HashMap.Entry {  

11.     Entry before, after;  

12.     ……  

13. }  

HashMap.Entry:

1. static class Entry implements Map.Entry {  

2.         final K key;  

3.         V value;  

4.         Entry next;  

5.         final int hash;  

6.   

7.         Entry(int h, K k, V v, Entry n) {  

8.             value = v;  

9.             next = n;  

10.             key = k;  

11.             hash = h;  

12.         }  

13. }  

    2) 初始化：

   通過源代碼可以看出，在LinkedHashMap的構(gòu)造方法中，實(shí)際調(diào)用了父類HashMap的相關(guān)構(gòu)造方法來構(gòu)造一個(gè)底層存放的table數(shù)組。如：

1. public LinkedHashMap(int initialCapacity, float loadFactor) {  

2.     super(initialCapacity, loadFactor);  

3.     accessOrder = false;  

4. }  

    HashMap中的相關(guān)構(gòu)造方法：

1. public HashMap(int initialCapacity, float loadFactor) {  

2.     if (initialCapacity < 0)  

3.         throw new IllegalArgumentException("Illegal initial capacity: " +  

4.                                            initialCapacity);  

5.     if (initialCapacity > MAXIMUM_CAPACITY)  

6.         initialCapacity = MAXIMUM_CAPACITY;  

7.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  

8.         throw new IllegalArgumentException("Illegal load factor: " +  

9.                                            loadFactor);  

10.   

11.     // Find a power of 2 >= initialCapacity  

12.     int capacity = 1;  

13.     while (capacity < initialCapacity)  

14.         capacity <<= 1;  

15.   

16.     this.loadFactor = loadFactor;  

17.     threshold = (int)(capacity * loadFactor);  

18.     table = new Entry[capacity];  

19.     init();  

20. }  

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

1. void init() {  

2.     header = new Entry(-1, null, null, null);  

3.     header.before = header.after = header;  

4. }  

    3) 存儲(chǔ)：

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

HashMap.put:

1. public V put(K key, V value) {  

2.         if (key == null)  

3.             return putForNullKey(value);  

4.         int hash = hash(key.hashCode());  

5.         int i = indexFor(hash, table.length);  

6.         for (Entry e = table[i]; e != null; e = e.next) {  

7.             Object k;  

8.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

9.                 V oldValue = e.value;  

10.                 e.value = value;  

11.                 e.recordAccess(this);  

12.                 return oldValue;  

13.             }  

14.         }  

15.   

16.         modCount++;  

17.         addEntry(hash, key, value, i);  

18.         return null;  

19.     }  

 重寫方法：

1. void recordAccess(HashMap m) {  

2.             LinkedHashMap lm = (LinkedHashMap)m;  

3.             if (lm.accessOrder) {  

4.                 lm.modCount++;  

5.                 remove();  

6.                 addBefore(lm.header);  

7.             }  

8.         }  

1. void addEntry(int hash, K key, V value, int bucketIndex) {  

2.     // 調(diào)用create方法，將新元素以雙向鏈表的的形式加入到映射中。  

3.     createEntry(hash, key, value, bucketIndex);  

4.   

5.     // 刪除最近最少使用元素的策略定義  

6.     Entry 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. void createEntry(int hash, K key, V value, int bucketIndex) {  

2.     HashMap.Entry old = table[bucketIndex];  

3.     Entry e = new Entry(hash, key, value, old);  

4.     table[bucketIndex] = e;  

5.     // 調(diào)用元素的addBrefore方法，將元素加入到哈希、雙向鏈接列表。  

6.     e.addBefore(header);  

7.     size++;  

8. }  

1. private void addBefore(Entry existingEntry) {  

2.     after  = existingEntry;  

3.     before = existingEntry.before;  

4.     before.after = this;  

5.     after.before = this;  

6. }  

4) 讀?。?/p>

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

HashMap.containsValue:

1. public boolean containsValue(Object value) {  

2.     if (value == null)  

3.             return containsNullValue();  

4.   

5.     Entry[] tab = table;  

6.         for (int i = 0; i < tab.length ; i++)  

7.             for (Entry e = tab[i] ; e != null ; e = e.next)  

8.                 if (value.equals(e.value))  

9.                     return true;  

10.     return false;  

11.     }  

1.  /*查找Map中是否包含給定的value，還是考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。 

2.  */  

3. public boolean containsValue(Object value) {  

4.         // Overridden to take advantage of faster iterator  

5.         if (value==null) {  

6.             for (Entry e = header.after; e != header; e = e.after)  

7.                 if (e.value==null)  

8.                     return true;  

9.         } else {  

10.             for (Entry e = header.after; e != header; e = e.after)  

11.                 if (value.equals(e.value))  

12.                     return true;  

13.         }  

14.         return false;  

15.     }  

1. /*該transfer()是HashMap中的實(shí)現(xiàn)：遍歷整個(gè)表的各個(gè)桶位，然后對桶進(jìn)行遍歷得到每一個(gè)Entry，重新hash到newTable中， 

2.  //放在這里是為了和下面LinkedHashMap重寫該法的比較， 

3.  void transfer(Entry[] newTable) { 

4.         Entry[] src = table; 

5.         int newCapacity = newTable.length; 

6.         for (int j = 0; j < src.length; j++) { 

7.             Entry e = src[j]; 

8.             if (e != null) { 

9.                 src[j] = null; 

10.                 do { 

11.                     Entry next = e.next; 

12.                     int i = indexFor(e.hash, newCapacity); 

13.                     e.next = newTable[i]; 

14.                     newTable[i] = e; 

15.                     e = next; 

16.                 } while (e != null); 

17.             } 

18.         } 

19.     } 

20.  */  

21.   

22.  /** 

23.  *transfer()方法是其父類HashMap調(diào)用resize()的時(shí)候調(diào)用的方法，它的作用是表擴(kuò)容后，把舊表中的key重新hash到新的表中。 

24.  *這里從寫了父類HashMap中的該方法，是因?yàn)榭紤]到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。 

25.  */  

26.  void transfer(HashMap.Entry[] newTable) {  

27.    int newCapacity = newTable.length;  

28.    for (Entry e = header.after; e != header; e = e.after) {  

29.      int index = indexFor(e.hash, newCapacity);  

30.      e.next = newTable[index];  

31.      newTable[index] = e;  

32.    }  

33.  }  

1. public V get(Object key) {  

2.     // 調(diào)用父類HashMap的getEntry()方法，取得要查找的元素。  

3.     Entry e = (Entry)getEntry(key);  

4.     if (e == null)  

5.         return null;  

6.     // 記錄訪問順序。  

7.     e.recordAccess(this);  

8.     return e.value;  

9. }  

1. void recordAccess(HashMap m) {  

2.     LinkedHashMap lm = (LinkedHashMap)m;  

3.     // 如果定義了LinkedHashMap的迭代順序?yàn)樵L問順序，  

4.     // 則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭。  

5.     if (lm.accessOrder) {  

6.         lm.modCount++;  

7.         remove();  

8.         addBefore(lm.header);  

9.     }  

10. }  

1. /** 

2.          * Removes this entry from the linked list. 

3.          */  

4.         private void remove() {  

5.             before.after = after;  

6.             after.before = before;  

7.         }  

1. /**clear鏈表，設(shè)置header為初始狀態(tài)*/  

2. public void clear() {  

3.  super.clear();  

4.  header.before = header.after = header;  

5. }  

    5) 排序模式：

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

1. private final boolean accessOrder;  

 一般情況下，不必指定排序模式，其迭代順序即為默認(rèn)為插入順序?？碙inkedHashMap的構(gòu)造方法，如：

1. public LinkedHashMap(int initialCapacity, float loadFactor) {  

2.     super(initialCapacity, loadFactor);  

3.     accessOrder = false;  

4. }  

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

1. public LinkedHashMap(int initialCapacity,  

2.          float loadFactor,  

3.                      boolean accessOrder) {  

4.     super(initialCapacity, loadFactor);  

5.     this.accessOrder = accessOrder;  

6. }  

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

當(dāng)有新元素加入Map的時(shí)候會(huì)調(diào)用Entry的addEntry方法，會(huì)調(diào)用removeEldestEntry方法，這里就是實(shí)現(xiàn)LRU元素過期機(jī)制的地方，默認(rèn)的情況下removeEldestEntry方法只返回false表示元素永遠(yuǎn)不過期。

1.   /** 

2.     * This override alters behavior of superclass put method. It causes newly 

3.     * allocated entry to get inserted at the end of the linked list and 

4.     * removes the eldest entry if appropriate. 

5.     */  

6.    void addEntry(int hash, K key, V value, int bucketIndex) {  

7.        createEntry(hash, key, value, bucketIndex);  

8.   

9.        // Remove eldest entry if instructed, else grow capacity if appropriate  

10.        Entry eldest = header.after;  

11.        if (removeEldestEntry(eldest)) {  

12.            removeEntryForKey(eldest.key);  

13.        } else {  

14.            if (size >= threshold)   

15.                resize(2 * table.length);  

16.        }  

17.    }  

18.   

19.    /** 

20.     * This override differs from addEntry in that it doesn't resize the 

21.     * table or remove the eldest entry. 

22.     */  

23.    void createEntry(int hash, K key, V value, int bucketIndex) {  

24.        HashMap.Entry old = table[bucketIndex];  

25. Entry e = new Entry(hash, key, value, old);  

26.        table[bucketIndex] = e;  

27.        e.addBefore(header);  

28.        size++;  

29.    }  

30.   

31.    protected boolean removeEldestEntry(Map.Entry eldest) {  

32.        return false;  

33.    }  

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

   例如：重寫此方法，維持此映射只保存100個(gè)條目的穩(wěn)定狀態(tài)，在每次添加新條目時(shí)刪除最舊的條目。

1. private static final int MAX_ENTRIES = 100;  

2. protected boolean removeEldestEntry(Map.Entry eldest) {  

3.     return size() > MAX_ENTRIES;  

4. }  

其實(shí)LinkedHashMap幾乎和HashMap一樣，不同的是它定義了一個(gè)Entry header，這個(gè)header不是放在Table里，它是額外獨(dú)立出來的。LinkedHashMap通過繼承hashMap中的Entry,并添加兩個(gè)屬性Entry  before,after,和header結(jié)合起來組成一個(gè)雙向鏈表，來實(shí)現(xiàn)按插入順序或訪問順序排序。