深入Java集合學(xué)習(xí)系列(四)

發(fā)布日期：2018-10-11 作者：atguigu 2465人瀏覽

2. LinkedHashMap的實現(xiàn)

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

1) Entry元素：

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

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的構(gòu)造方法中，實際調(diào)用了父類HashMap的相關(guān)構(gòu)造方法來構(gòu)造一個底層存放的table數(shù)組。如：

Java代碼?

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

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

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

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

LinkedHashMap重寫了init()方法，在調(diào)用父類的構(gòu)造方法完成構(gòu)造后，進(jìn)一步實現(xiàn)了對其元素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方法調(diào)用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的雙向鏈接列表的實現(xiàn)。

Java代碼?

  1. voidaddEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{??
  2. //?調(diào)用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. //?調(diào)用元素的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) 讀?。?/b>

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

Java代碼?

  1. publicV?get(Object?key)?{??
  2. //?調(diào)用父類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;??

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

Java代碼?

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

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

Java代碼?

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

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

Java代碼?

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

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

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

Java代碼?

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