2. LinkedHashMap的實現

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

1) Entry元素：

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

Java代碼?

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

2) 初始化：

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

Java代碼?

1. publicLinkedHashMap(int?initialCapacity,?float?loadFactor)?{??
2. super(initialCapacity,?loadFactor);??
3. accessOrder?=?false;??
4. }??

HashMap中的相關構造方法：

Java代碼?

1. publicHashMap(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的初始化操作。

Java代碼?

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

3) 存儲：

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

Java代碼?

1. voidaddEntry(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. }??

Java代碼?

1. voidcreateEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{??
2. 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. addBefore(header);??
7. size++;??
8. }??

Java代碼?

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

4) 讀取：

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

Java代碼?

1. publicV?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. recordAccess(this);??
8. returnvalue;??
9. }??

Java代碼?

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

5) 排序模式：

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

Java代碼?

1. privatefinal?boolean?accessOrder;??

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

Java代碼?

1. publicLinkedHashMap(int?initialCapacity,?float?loadFactor)?{??
2. super(initialCapacity,?loadFactor);??
3. accessOrder?=?false;??
4. }??

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

Java代碼?

1. publicLinkedHashMap(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)方法，在將新條目插入到映射后，put和 putAll將調用此方法。該方法可以提供在每次添加新條目時移除最舊條目的實現程序，默認返回false，這樣，此映射的行為將類似于正常映射，即永遠不能移除最舊的元素。

Java代碼?

1. protectedboolean?removeEldestEntry(Map.Entry<K,V>?eldest)?{??
2. return?false;??
3. }??

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

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

Java代碼?

1. privatestatic?final?int?MAX_ENTRIES?=?100;??
2. protectedboolean?removeEldestEntry(Map.Entry?eldest)?{??
3. return?size()?>?MAX_ENTRIES;??
4. }??