【源代碼】LinkedHashMap源代碼剖析

注：下面源代碼基于jdk1.7.0_11

之前的兩篇文章通過源代碼分析了兩種常見的Map集合，HashMap和Hashtable。本文将繼續介紹還有一種Map集合——LinkedHashMap。

顧名思義，LinkedHashMap除了是一個HashMap之外。還帶有LinkedList的特點。也就是說可以保持周遊的順序和插入的順序一緻，那麼它是怎麼做到的呢？以下我們開始分析。

首先看構造器。

LinkedHashMap直接繼承自HashMap，是以擁有HashMap的大部分特性。比方支援null鍵和值，預設容量為16。裝載因子為0.75。非線程安全等等。

可是LinkedHashMap還有非常多個性的地方，以下來看成員變量：

LinkedHashMap比HashMap多了兩個成員變量，當中header代表内部雙向連結清單的頭結點。後面我們就會發現，LinkedHashMap除了有個桶數組容納全部Entry之外，另一個雙向連結清單儲存全部Entry引用。

周遊的時候。并非去周遊桶數組，而是直接周遊雙向連結清單，是以LinkedHashMap的周遊時間不受桶容量的限制，這是它和HashMap的重要差别之中的一個。

而這個accessOrder代表的是是否依照訪問順序，true代表是，預設是插入順序。是以我們能夠将accessOrder置為true來實作LRU算法，這能夠用來做緩存。

再看構造器：

構造器首先都會調用父類也就是HashMap的構造器來初始化桶數組，而accessOrder之後會被初始化，除了最後面的一個構造器同意指定accessOrder外。其它構造器都預設将accessOrder置為了false。

讀者可能非常奇怪，不是還有個header麼。這個雙向連結清單為啥不在構造器中初始化呢？這得回到HashMap中檢視hashMap的構造器了：

HashMap構造器最後一步調用了一個init方法，而這個init方法在HashMap中是個空實作，沒有不論什麼代碼。

這事實上就是所謂的“鈎子”，詳細代碼由子類實作，假設子類希望每次構造的時候都去做一些特定的初始化操作，能夠選擇複寫init方法。

我們看到LinkedHashMap中确實複寫了init：

在init方法中，果然初始化了雙向連結清單。并且我們還發現，這不光是個雙向連結清單，還是個循環連結清單。

HashMap内部的Entry類并沒有before和after指針，也就是說LinkedHashMap自己重寫了一個Entry類：

這裡的Entry選擇繼承父類的Entry類，也就是說LinkedHashMap中的Entry擁有三個指針。除了前驅後繼指針外用于雙向連結清單的連接配接外。另一個next指針用于解決hash沖突（引用鍊）。

除此之外，Entry新增了幾個方法，remove和addbefore用來操作雙向連結清單不用多說。而recordAccess方法比較特殊，這種方法在HashMap中也是空實作，并在put方法中會調用此方法：

此外，在LinkedHashMap的get方法中，也會調用此方法：

也就是說，僅僅要涉及到訪問結點。那麼就會調用這種方法。

觀察該方法的邏輯：假設accessOrder為true，那麼會調用addBefore方法将目前Entry放到雙向連結清單的尾部，終于在我們周遊連結清單的時候就會發現最近最少使用的結點的都集中在連結清單頭部（從最近訪問最少到最近訪問最多的順序）。這就是LRU。

LinkedHashMap并沒有複寫put方法，可是卻複寫了addEntry和createEntry方法，之前分析HashMap的時候我們就知道了。put方法會調用addEntry将鍵值對挂到桶的某個合适位置，而addEntry又會調用createEntry方法建立一個鍵值對對象。因而，LinkedHashMap事實上是間接更改了put方法，想想也非常easy了解，LinkedHashMap除了要向桶中加入鍵值對外，還需向連結清單中添加鍵值對，是以必須得改動put方法。

createEntry方法會将鍵值對分别挂到桶數組和雙向連結清單中。

比較有意思的是addEntry方法。它提供了一個可選的操作。我們能夠通過繼承LinkedHashMap并複寫removeEldestEntry方法讓該子類能夠自己主動地删除近期最少訪問的鍵值對——這能夠用來做緩存!!

LinkedHashMap自己定義了疊代器以及疊代規則。LinkedHashMap是通過内部的雙向連結清單來完畢疊代的。周遊時間與鍵值對總數成正比，而HashMap周遊時間與容量成正比，是以通常情況下。LinkedHashMap周遊性能是優于HashMap的。可是由于須要額外維護連結清單。是以折中來看，兩者性能相差無幾。

總結：

1.LinkedHashMap繼承自HashMap。具有HashMap的大部分特性，比方支援null鍵和值。預設容量為16，裝載因子為0.75，非線程安全等等；

2.LinkedHashMap通過設定accessOrder控制周遊順序是依照插入順序還是依照訪問順序。當accessOrder為true時。能夠利用其完畢LRU緩存的功能；

3.LinkedHashMap内部維護了一個雙向循環連結清單，而且其疊代操作時通過連結清單完畢的。而不是去周遊hash表。