LinkedHashMap是Map接口的哈希表和鏈接列表實(shí)現(xiàn)，具有可預(yù)知的迭代順序。允許使用null值和null鍵。

LinkedHashMap實(shí)現(xiàn)與HashMap的不同之處在于，后者維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問(wèn)順序。

對(duì)于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向鏈表來(lái)保存所有元素。其基本操作與父類(lèi)HashMap相似，它通過(guò)重寫(xiě)父類(lèi)相關(guān)的方法，來(lái)實(shí)現(xiàn)自己的鏈接列表特性。

/**  * 雙向鏈表的表頭元素。  */  PRivate transient Entry<K,V> header;    /**  * LinkedHashMap的Entry元素。  * 繼承HashMap的Entry元素，又保存了其上一個(gè)元素before和下一個(gè)元素after的引用。  */  private static class Entry<K,V> extends HashMap.Entry<K,V> {      Entry<K,V> before, after;      &hellip;…  }

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

public LinkedHashMap(int initialCapacity, float loadFactor) {      super(initialCapacity, loadFactor);      accessOrder = false;  }

在LinkedHashMap的構(gòu)造方法中，實(shí)際調(diào)用了父類(lèi)HashMap的相關(guān)構(gòu)造方法來(lái)構(gòu)造一個(gè)底層存放的table數(shù)組。

void init() {      header = new Entry<K,V>(-1, null, null, null);      header.before = header.after = header;  }

void addEntry(int hash, K key, V value, int bucketIndex) {      // 調(diào)用create方法，將新元素以雙向鏈表的的形式加入到映射中。      createEntry(hash, key, value, bucketIndex);        // 刪除最近最少使用元素的策略定義      Entry<K,V> eldest = header.after;      if (removeEldestEntry(eldest)) {          removeEntryForKey(eldest.key);      } else {          if (size >= threshold)              resize(2 * table.length);      }  }

void createEntry(int hash, K key, V value, int bucketIndex) {      HashMap.Entry<K,V> old = table[bucketIndex];      Entry<K,V> e = new Entry<K,V>(hash, key, value, old);      table[bucketIndex] = e;      // 調(diào)用元素的addBrefore方法，將元素加入到哈希、雙向鏈接列表。      e.addBefore(header);      size++;  }

private void addBefore(Entry<K,V> existingEntry) {      after  = existingEntry;      before = existingEntry.before;      before.after = this;      after.before = this;  }

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

public V get(Object key) {      // 調(diào)用父類(lèi)HashMap的getEntry()方法，取得要查找的元素。      Entry<K,V> e = (Entry<K,V>)getEntry(key);      if (e == null)          return null;      // 記錄訪問(wèn)順序。      e.recordAccess(this);      return e.value;  }

void recordAccess(HashMap<K,V> m) {      LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;      // 如果定義了LinkedHashMap的迭代順序?yàn)樵L問(wèn)順序，      // 則刪除以前位置上的元素，并將最新訪問(wèn)的元素添加到鏈表表頭。      if (lm.accessOrder) {          lm.modCount++;          remove();          addBefore(lm.header);      }  }

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

private final boolean accessOrder;

一般情況下，不必指定排序模式，其迭代順序即為默認(rèn)為插入順序。

public LinkedHashMap(int initialCapacity, float loadFactor) {      super(initialCapacity, loadFactor);      accessOrder = false;  }

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

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {      super(initialCapacity, loadFactor);      this.accessOrder = accessOrder;  }

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

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {      return false;  }

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