LinkedHashMap 的實(shí)現(xiàn)原理
LinkedHashMap 概述
HashMap 是無序的，HashMap 在 put 的時(shí)候是根據(jù) key 的 hashcode 進(jìn)行 hash 然后放入對(duì)應(yīng)的地方。所以在按照一定順序 put 進(jìn) HashMap 中笛厦，然后遍歷出 HashMap 的順序跟 put 的順序不同（除非在 put 的時(shí)候 key 已經(jīng)按照 hashcode 排序號(hào)了赎瞎，這種幾率非常型慊恪）
JAVA 在 JDK1.4 以后提供了 LinkedHashMap 來幫助我們實(shí)現(xiàn)了有序的 HashMap！
LinkedHashMap 是 HashMap 的一個(gè)子類，它保留插入的順序访诱，如果需要輸出的順序和輸入時(shí)的相同，那么就選用 LinkedHashMap韩肝。
LinkedHashMap 是 Map 接口的哈希表和鏈接列表實(shí)現(xiàn)触菜，具有可預(yù)知的迭代順序。此實(shí)現(xiàn)提供所有可選的映射操作哀峻，并允許使用 null 值和 null 鍵涡相。此類不保證映射的順序，特別是它不保證該順序恒久不變剩蟀。
LinkedHashMap 實(shí)現(xiàn)與 HashMap 的不同之處在于催蝗，LinkedHashMap 維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序育特，該迭代順序可以是插入順序或者是訪問順序丙号。
注意，此實(shí)現(xiàn)不是同步的缰冤。如果多個(gè)線程同時(shí)訪問鏈接的哈希映射犬缨，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步棉浸。
根據(jù)鏈表中元素的順序可以分為：按插入順序的鏈表怀薛，和按訪問順序(調(diào)用 get 方法)的鏈表。默認(rèn)是按插入順序排序迷郑，如果指定按訪問順序排序枝恋，那么調(diào)用get方法后，會(huì)將這次訪問的元素移至鏈表尾部嗡害，不斷訪問可以形成按訪問順序排序的鏈表焚碌。
小 Demo
我在最開始學(xué)習(xí) LinkedHashMap 的時(shí)候，看到訪問順序就漾、插入順序等等呐能，有點(diǎn)暈了，隨著后續(xù)的學(xué)習(xí)才慢慢懂得其中原理，所以我會(huì)先在進(jìn)行做幾個(gè) demo 來演示一下 LinkedHashMap 的使用摆出±驶玻看懂了其效果，然后再來研究其原理偎漫。
HashMap
看下面這個(gè)代碼：
public static void main(String[] args) {
? ? Map map = new HashMap();
? ? map.put("apple", "蘋果");
? ? map.put("watermelon", "西瓜");
? ? map.put("banana", "香蕉");
? ? map.put("peach", "桃子");
? ? Iterator iter = map.entrySet().iterator();
? ? while (iter.hasNext()) {
? ? ? ? Map.Entry entry = (Map.Entry) iter.next();
? ? ? ? System.out.println(entry.getKey() + "=" + entry.getValue());
? ? }
}
一個(gè)比較簡單的測試 HashMap 的代碼爷恳，通過控制臺(tái)的輸出，我們可以看到 HashMap 是沒有順序的象踊。
banana=香蕉
apple=蘋果
peach=桃子
watermelon=西瓜
LinkedHashMap
我們現(xiàn)在將 map 的實(shí)現(xiàn)換成 LinkedHashMap温亲，其他代碼不變：Map map = new LinkedHashMap();
看一下控制臺(tái)的輸出：
apple=蘋果
watermelon=西瓜
banana=香蕉
peach=桃子
我們可以看到，其輸出順序是完成按照插入順序的杯矩！也就是我們上面所說的保留了插入的順序栈虚。我們不是在上面還提到過其可以按照訪問順序進(jìn)行排序么？好的史隆，我們還是通過一個(gè)例子來驗(yàn)證一下：
public static void main(String[] args) {
? ? Map map = new LinkedHashMap(16,0.75f,true);
? ? map.put("apple", "蘋果");
? ? map.put("watermelon", "西瓜");
? ? map.put("banana", "香蕉");
? ? map.put("peach", "桃子");
? ? map.get("banana");
? ? map.get("apple");
? ? Iterator iter = map.entrySet().iterator();
? ? while (iter.hasNext()) {
? ? ? ? Map.Entry entry = (Map.Entry) iter.next();
? ? ? ? System.out.println(entry.getKey() + "=" + entry.getValue());
? ? }
}
代碼與之前的都差不多魂务，但我們多了兩行代碼，并且初始化 LinkedHashMap 的時(shí)候泌射，用的構(gòu)造函數(shù)也不相同粘姜，看一下控制臺(tái)的輸出結(jié)果：
watermelon=西瓜
peach=桃子
banana=香蕉
apple=蘋果
這也就是我們之前提到過的，LinkedHashMap 可以選擇按照訪問順序進(jìn)行排序熔酷。
LinkedHashMap 的實(shí)現(xiàn)
對(duì)于 LinkedHashMap 而言孤紧，它繼承與 HashMap(public class LinkedHashMap extends HashMap implements Map)、底層使用哈希表與雙向鏈表來保存所有元素拒秘。其基本操作與父類 HashMap 相似号显，它通過重寫父類相關(guān)的方法，來實(shí)現(xiàn)自己的鏈接列表特性翼抠。下面我們來分析 LinkedHashMap 的源代碼：
成員變量
LinkedHashMap 采用的 hash 算法和 HashMap 相同咙轩，但是它重新定義了數(shù)組中保存的元素 Entry，該 Entry 除了保存當(dāng)前對(duì)象的引用外阴颖，還保存了其上一個(gè)元素 before 和下一個(gè)元素 after 的引用活喊，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表×坷ⅲ看源代碼：
/**
* The iteration ordering method for this linked hash map: true
* for access-order, false for insertion-order.
* 如果為true钾菊，則按照訪問順序；如果為false偎肃，則按照插入順序煞烫。
*/
private final boolean accessOrder;
/**
* 雙向鏈表的表頭元素。
*/
private transient Entry header;
/**
* LinkedHashMap的Entry元素累颂。
* 繼承HashMap的Entry元素滞详，又保存了其上一個(gè)元素before和下一個(gè)元素after的引用凛俱。
*/
private static class Entry extends HashMap.Entry {
? ? Entry before, after;
? ? ……
}
LinkedHashMap 中的 Entry 集成與 HashMap 的 Entry，但是其增加了 before 和 after 的引用料饥，指的是上一個(gè)元素和下一個(gè)元素的引用蒲犬。
初始化
通過源代碼可以看出，在 LinkedHashMap 的構(gòu)造方法中岸啡，實(shí)際調(diào)用了父類 HashMap 的相關(guān)構(gòu)造方法來構(gòu)造一個(gè)底層存放的 table 數(shù)組原叮，但額外可以增加 accessOrder 這個(gè)參數(shù)，如果不設(shè)置巡蘸，默認(rèn)為 false奋隶，代表按照插入順序進(jìn)行迭代；當(dāng)然可以顯式設(shè)置為 true悦荒，代表以訪問順序進(jìn)行迭代唯欣。如：
public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) {
? ? super(initialCapacity, loadFactor);
? ? this.accessOrder = accessOrder;
}
我們已經(jīng)知道 LinkedHashMap 的 Entry 元素繼承 HashMap 的 Entry，提供了雙向鏈表的功能逾冬。在上述 HashMap 的構(gòu)造器中黍聂，最后會(huì)調(diào)用 init() 方法，進(jìn)行相關(guān)的初始化身腻，這個(gè)方法在 HashMap 的實(shí)現(xiàn)中并無意義，只是提供給子類實(shí)現(xiàn)相關(guān)的初始化調(diào)用匹厘。
但在 LinkedHashMap 重寫了 init() 方法嘀趟，在調(diào)用父類的構(gòu)造方法完成構(gòu)造后，進(jìn)一步實(shí)現(xiàn)了對(duì)其元素 Entry 的初始化操作愈诚。
/**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map.? Initializes
* the chain.
*/
@Override
void init() {
? header = new Entry<>(-1, null, null, null);
? header.before = header.after = header;
}
存儲(chǔ)
LinkedHashMap 并未重寫父類 HashMap 的 put 方法她按，而是重寫了父類 HashMap 的 put 方法調(diào)用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)炕柔，提供了自己特有的雙向鏈接列表的實(shí)現(xiàn)酌泰。我們?cè)谥暗奈恼轮幸呀?jīng)講解了HashMap的put方法，我們?cè)谶@里重新貼一下 HashMap 的 put 方法的源代碼：
HashMap.put:
public V put(K key, V value) {
? ? ? ? if (key == null)
? ? ? ? ? ? return putForNullKey(value);
? ? ? ? int hash = hash(key);
? ? ? ? int i = indexFor(hash, table.length);
? ? ? ? for (Entry e = table[i]; e != null; e = e.next) {
? ? ? ? ? ? Object k;
? ? ? ? ? ? if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
? ? ? ? ? ? ? ? V oldValue = e.value;
? ? ? ? ? ? ? ? e.value = value;
? ? ? ? ? ? ? ? e.recordAccess(this);
? ? ? ? ? ? ? ? return oldValue;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? modCount++;
? ? ? ? addEntry(hash, key, value, i);
? ? ? ? return null;
}
重寫方法：
void recordAccess(HashMap m) {
? ? LinkedHashMap lm = (LinkedHashMap)m;
? ? if (lm.accessOrder) {
? ? ? ? lm.modCount++;
? ? ? ? remove();
? ? ? ? addBefore(lm.header);
? ? ? ? }
}
void addEntry(int hash, K key, V value, int bucketIndex) {
? ? // 調(diào)用create方法匕累，將新元素以雙向鏈表的的形式加入到映射中陵刹。
? ? createEntry(hash, key, value, bucketIndex);
? ? // 刪除最近最少使用元素的策略定義
? ? Entry 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 old = table[bucketIndex];
? ? Entry e = new Entry(hash, key, value, old);
? ? table[bucketIndex] = e;
? ? // 調(diào)用元素的addBrefore方法，將元素加入到哈希欢嘿、雙向鏈接列表衰琐。?
? ? e.addBefore(header);
? ? size++;
}
private void addBefore(Entry existingEntry) {
? ? after? = existingEntry;
? ? before = existingEntry.before;
? ? before.after = this;
? ? after.before = this;
}
讀取
LinkedHashMap 重寫了父類 HashMap 的 get 方法，實(shí)際在調(diào)用父類 getEntry() 方法取得查找的元素后炼蹦，再判斷當(dāng)排序模式 accessOrder 為 true 時(shí)羡宙，記錄訪問順序，將最新訪問的元素添加到雙向鏈表的表頭掐隐，并從原來的位置刪除狗热。由于的鏈表的增加、刪除操作是常量級(jí)的，故并不會(huì)帶來性能的損失匿刮。
public V get(Object key) {
? ? // 調(diào)用父類HashMap的getEntry()方法僧凰，取得要查找的元素。
? ? Entry e = (Entry)getEntry(key);
? ? if (e == null)
? ? ? ? return null;
? ? // 記錄訪問順序僻焚。
? ? e.recordAccess(this);
? ? return e.value;
}
void recordAccess(HashMap m) {
? ? LinkedHashMap lm = (LinkedHashMap)m;
? ? // 如果定義了LinkedHashMap的迭代順序?yàn)樵L問順序允悦，
? ? // 則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭虑啤。?
? ? if (lm.accessOrder) {
? ? ? ? lm.modCount++;
? ? ? ? remove();
? ? ? ? addBefore(lm.header);
? ? }
}
/**
* Removes this entry from the linked list.
*/
private void remove() {
? ? before.after = after;
? ? after.before = before;
}
/**clear鏈表隙弛，設(shè)置header為初始狀態(tài)*/
public void clear() {
super.clear();
header.before = header.after = header;
}
排序模式
LinkedHashMap 定義了排序模式 accessOrder，該屬性為 boolean 型變量狞山，對(duì)于訪問順序全闷，為 true；對(duì)于插入順序萍启，則為 false总珠。一般情況下，不必指定排序模式勘纯，其迭代順序即為默認(rèn)為插入順序局服。
這些構(gòu)造方法都會(huì)默認(rèn)指定排序模式為插入順序。如果你想構(gòu)造一個(gè) LinkedHashMap驳遵，并打算按從近期訪問最少到近期訪問最多的順序（即訪問順序）來保存元素淫奔，那么請(qǐng)使用下面的構(gòu)造方法構(gòu)造 LinkedHashMap：public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
該哈希映射的迭代順序就是最后訪問其條目的順序，這種映射很適合構(gòu)建 LRU 緩存堤结。LinkedHashMap 提供了 removeEldestEntry(Map.Entry eldest) 方法唆迁。該方法可以提供在每次添加新條目時(shí)移除最舊條目的實(shí)現(xiàn)程序，默認(rèn)返回 false竞穷，這樣唐责，此映射的行為將類似于正常映射，即永遠(yuǎn)不能移除最舊的元素瘾带。
我們會(huì)在后面的文章中詳細(xì)介紹關(guān)于如何用 LinkedHashMap 構(gòu)建 LRU 緩存鼠哥。
總結(jié)
其實(shí) LinkedHashMap 幾乎和 HashMap 一樣：從技術(shù)上來說，不同的是它定義了一個(gè) Entry header月弛，這個(gè) header 不是放在 Table 里肴盏，它是額外獨(dú)立出來的。LinkedHashMap 通過繼承 hashMap 中的 Entry,并添加兩個(gè)屬性 Entry before,after,和 header 結(jié)合起來組成一個(gè)雙向鏈表帽衙，來實(shí)現(xiàn)按插入順序或訪問順序排序菜皂。
在寫關(guān)于 LinkedHashMap 的過程中，記起來之前面試的過程中遇到的一個(gè)問題厉萝，也是問我 Map 的哪種實(shí)現(xiàn)可以做到按照插入順序進(jìn)行迭代恍飘？當(dāng)時(shí)腦子是突然短路的榨崩，但現(xiàn)在想想，也只能怪自己對(duì)這個(gè)知識(shí)點(diǎn)還是掌握的不夠扎實(shí)章母，所以又從頭認(rèn)真的把代碼看了一遍母蛛。
不過，我的建議是乳怎，大家首先首先需要記住的是：LinkedHashMap 能夠做到按照插入順序或者訪問順序進(jìn)行迭代彩郊，這樣在我們以后的開發(fā)中遇到相似的問題，才能想到用 LinkedHashMap 來解決蚪缀，否則就算對(duì)其內(nèi)部結(jié)構(gòu)非常了解秫逝，不去使用也是沒有什么用的。
我們學(xué)習(xí)的目的是為了更好的應(yīng)用询枚。
出處：http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
