Java 集合系列(四)LinkedHashMap 實現(xiàn)原理

LinkedHashMap 實現(xiàn)原理

集合

1. LinkedHashMap 概述

????????LinkedHashMap 是 Map 接口的哈希表和鏈接列表實現(xiàn)称近，具有可預知的迭代順序。此實現(xiàn)提供所有可選的映射操作仆百，并允許使用null 值和 null 鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。

????????LinkedHashMap 實現(xiàn)與 HashMap 的不同之處在于辫诅，后者維護著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序涧狮，該迭代順序可以是插入順序或者是訪問順序炕矮。

????????注意，此實現(xiàn)不是同步的者冤。如果多個線程同時訪問鏈接的哈希映射肤视，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步譬嚣。

2. LinkedHashMap 的實現(xiàn)

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

1) Entry 元素

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

2) 初始化

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

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

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

????????LinkedHashMap 重寫了 init()方法棱烂，在調(diào)用父類的構(gòu)造方法完成構(gòu)造后租漂，進一步實現(xiàn)了對其元素Entry 的初始化操作。

3) 存儲

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

4) 讀取

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

5) 排序模式

????????LinkedHashMap 定義了排序模式 accessOrder霉颠，該屬性為 boolean 型變量对碌，對于訪問順序，為true蒿偎；對于插入順序朽们，則為 false。

??private final boolean accessOrder;

????????一般情況下诉位，不必指定排序模式骑脱，其迭代順序即為默認為插入順序〔钥罚看 LinkedHashMap的構(gòu)造方法叁丧，如：

public LinkedHashMap(int initialCapacity, float loadFactor) {

????super(initialCapacity, loadFactor);

? ? ?accessOrder = false;

?}

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

public LinkedHashMap(int initialCapacity,

????float loadFactor,

????boolean accessOrder) {

????super(initialCapacity, loadFactor);

????this.accessOrder = accessOrder;

}

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

protected boolean removeEldestEntry(Map.Entry eldest) {

????return false;

}

????????此方法通常不以任何方式修改映射，相反允許映射在其返回值的指引下進行自我修改摊沉。如果用此映射構(gòu)建LRU 緩存狐史，則非常方便，它允許映射通過刪除舊條目來減少內(nèi)存損耗说墨。例如：重寫此方法骏全，維持此映射只保存100 個條目的穩(wěn)定狀態(tài)，在每次添加新條目時刪除最舊的條目尼斧。

private static final int MAX_ENTRIES = 100;

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

????return size() > MAX_ENTRIES;

}