理解LinkedHashMap

1. LinkedHashMap概述：

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

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

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

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

2. LinkedHashMap的實現：

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

類結構：

1. public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>    

 1) 成員變量：

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

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

2.  private final boolean accessOrder;  

1. /** 

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

3.  */  

4. private transient Entry<K,V> header;  

5.   

6. /** 

7.  * LinkedHashMap的Entry元素。 

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

9.  */  

10. private static class Entry<K,V> extends HashMap.Entry<K,V> {  

11.     Entry<K,V> before, after;  

12.     ……  

13. }  

HashMap.Entry:

1. static class Entry<K,V> implements Map.Entry<K,V> {  

2.         final K key;  

3.         V value;  

4.         Entry<K,V> next;  

5.         final int hash;  

6.   

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

8.             value = v;  

9.             next = n;  

10.             key = k;  

11.             hash = h;  

12.         }  

13. }  

    2) 初始化：

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

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

2.     super(initialCapacity, loadFactor);  

3.     accessOrder = false;  

4. }  

    HashMap中的相關構造方法：

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. }  

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

1. void init() {  

2.     header = new Entry<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. 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<K,V> 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<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. void addEntry(int hash, K key, V value, int bucketIndex) {  

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

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

4.   

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

2.     HashMap.Entry<K,V> old = table[bucketIndex];  

3.     Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  

4.     table[bucketIndex] = e;  

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

6.     e.addBefore(header);  

7.     size++;  

8. }  

1. private void addBefore(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. 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中的實現：遍歷整個表的各個桶位，然后對桶進行遍歷得到每一個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<K,V> e = src[j]; 

8.             if (e != null) { 

9.                 src[j] = null; 

10.                 do { 

11.                     Entry<K,V> 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調用resize()的時候調用的方法，它的作用是表擴容后，把舊表中的key重新hash到新的表中。 

24.  *這里從寫了父類HashMap中的該方法，是因為考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。 

25.  */  

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

27.    int newCapacity = newTable.length;  

28.    for (Entry<K, V> 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.     // 調用父類HashMap的getEntry()方法，取得要查找的元素。  

3.     Entry<K,V> e = (Entry<K,V>)getEntry(key);  

4.     if (e == null)  

5.         return null;  

6.     // 記錄訪問順序。  

7.     e.recordAccess(this);  

8.     return e.value;  

9. }  

1. void recordAccess(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.          * Removes this entry from the linked list. 

3.          */  

4.         private void remove() {  

5.             before.after = after;  

6.             after.before = before;  

7.         }  

1. /**clear鏈表，設置header為初始狀態*/  

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;  

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

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

2.     super(initialCapacity, loadFactor);  

3.     accessOrder = false;  

4. }  

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

1. public LinkedHashMap(int initialCapacity,  

2.          float loadFactor,  

3.                      boolean accessOrder) {  

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.     * 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<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.    }  

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<K,V> old = table[bucketIndex];  

25. Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  

26.        table[bucketIndex] = e;  

27.        e.addBefore(header);  

28.        size++;  

29.    }  

30.   

31.    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {  

32.        return false;  

33.    }  

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

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

1. private static final int MAX_ENTRIES = 100;  

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

3.     return size() > MAX_ENTRIES;  

4. }  

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