HashMap 是無(wú)序的，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)了，這種幾率非常?。?/p>
JAVA 在 JDK1.4 以后提供了 LinkedHashMap 來(lái)幫助我們實(shí)現(xiàn)了有序的 HashMap！
LinkedHashMap 是 HashMap 的一個(gè)子類(lèi)，它保留插入的順序，如果需要輸出的順序和輸入時(shí)的相同，那么就選用 LinkedHashMap。
LinkedHashMap 是 Map 接口的哈希表和鏈接列表實(shí)現(xiàn)，具有可預(yù)知的迭代順序。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用 null 值和 null 鍵。此類(lèi)不保證映射的順序，特別是它不保證該順序恒久不變。
LinkedHashMap 實(shí)現(xiàn)與 HashMap 的不同之處在于，LinkedHashMap 維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問(wèn)順序。
注意，此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問(wèn)鏈接的哈希映射，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步。
根據(jù)鏈表中元素的順序可以分為：按插入順序的鏈表，和按訪問(wèn)順序(調(diào)用 get 方法)的鏈表。默認(rèn)是按插入順序排序，如果指定按訪問(wèn)順序排序，那么調(diào)用get方法后，會(huì)將這次訪問(wèn)的元素移至鏈表尾部，不斷訪問(wèn)可以形成按訪問(wèn)順序排序的鏈表。
我在最開(kāi)始學(xué)習(xí) LinkedHashMap 的時(shí)候，看到訪問(wèn)順序、插入順序等等，有點(diǎn)暈了，隨著后續(xù)的學(xué)習(xí)才慢慢懂得其中原理，所以我會(huì)先在進(jìn)行做幾個(gè) demo 來(lái)演示一下 LinkedHashMap 的使用。看懂了其效果，然后再來(lái)研究其原理。
看下面這個(gè)代碼：
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("apple", "蘋(píng)果");
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è)比較簡(jiǎn)單的測(cè)試 HashMap 的代碼，通過(guò)控制臺(tái)的輸出，我們可以看到 HashMap 是沒(méi)有順序的。
banana=香蕉
apple=蘋(píng)果
peach=桃子
watermelon=西瓜我們現(xiàn)在將 map 的實(shí)現(xiàn)換成 LinkedHashMap，其他代碼不變：Map<String, String> map = new LinkedHashMap<String, String>();
看一下控制臺(tái)的輸出：
apple=蘋(píng)果
watermelon=西瓜
banana=香蕉
peach=桃子我們可以看到，其輸出順序是完成按照插入順序的！也就是我們上面所說(shuō)的保留了插入的順序。我們不是在上面還提到過(guò)其可以按照訪問(wèn)順序進(jìn)行排序么？好的，我們還是通過(guò)一個(gè)例子來(lái)驗(yàn)證一下：
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "蘋(píng)果");
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=蘋(píng)果這也就是我們之前提到過(guò)的，LinkedHashMap 可以選擇按照訪問(wèn)順序進(jìn)行排序。
對(duì)于 LinkedHashMap 而言，它繼承與 HashMap(public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>)、底層使用哈希表與雙向鏈表來(lái)保存所有元素。其基本操作與父類(lèi) HashMap 相似，它通過(guò)重寫(xiě)父類(lèi)相關(guān)的方法，來(lái)實(shí)現(xiàn)自己的鏈接列表特性。下面我們來(lái)分析 LinkedHashMap 的源代碼：
LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是它重新定義了數(shù)組中保存的元素 Entry，該 Entry 除了保存當(dāng)前對(duì)象的引用外，還保存了其上一個(gè)元素 before 和下一個(gè)元素 after 的引用，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表?？丛创a：
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* 如果為true，則按照訪問(wèn)順序；如果為false，則按照插入順序。
*/
private final boolean accessOrder;
/**
* 雙向鏈表的表頭元素。
*/
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;
……
}LinkedHashMap 中的 Entry 集成與 HashMap 的 Entry，但是其增加了 before 和 after 的引用，指的是上一個(gè)元素和下一個(gè)元素的引用。
通過(guò)源代碼可以看出，在 LinkedHashMap 的構(gòu)造方法中，實(shí)際調(diào)用了父類(lèi) HashMap 的相關(guān)構(gòu)造方法來(lái)構(gòu)造一個(gè)底層存放的 table 數(shù)組，但額外可以增加 accessOrder 這個(gè)參數(shù)，如果不設(shè)置，默認(rèn)為 false，代表按照插入順序進(jìn)行迭代；當(dāng)然可以顯式設(shè)置為 true，代表以訪問(wèn)順序進(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)中并無(wú)意義，只是提供給子類(lèi)實(shí)現(xiàn)相關(guān)的初始化調(diào)用。
但在 LinkedHashMap 重寫(xiě)了 init() 方法，在調(diào)用父類(lèi)的構(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;
}LinkedHashMap 并未重寫(xiě)父類(lèi) HashMap 的 put 方法，而是重寫(xiě)了父類(lèi) 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<K,V> 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;
}重寫(xiě)方法：
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)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<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 的 get 方法，實(shí)際在調(diào)用父類(lèi) getEntry() 方法取得查找的元素后，再判斷當(dāng)排序模式 accessOrder 為 true 時(shí)，記錄訪問(wèn)順序，將最新訪問(wèn)的元素添加到雙向鏈表的表頭，并從原來(lái)的位置刪除。由于的鏈表的增加、刪除操作是常量級(jí)的，故并不會(huì)帶來(lái)性能的損失。
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);
}
}
/**
* 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ì)于訪問(wèn)順序，為 true；對(duì)于插入順序，則為 false。一般情況下，不必指定排序模式，其迭代順序即為默認(rèn)為插入順序。
這些構(gòu)造方法都會(huì)默認(rèn)指定排序模式為插入順序。如果你想構(gòu)造一個(gè) LinkedHashMap，并打算按從近期訪問(wèn)最少到近期訪問(wèn)最多的順序（即訪問(wèn)順序）來(lái)保存元素，那么請(qǐng)使用下面的構(gòu)造方法構(gòu)造 LinkedHashMap：public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
該哈希映射的迭代順序就是最后訪問(wèn)其條目的順序，這種映射很適合構(gòu)建 LRU 緩存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。該方法可以提供在每次添加新條目時(shí)移除最舊條目的實(shí)現(xiàn)程序，默認(rèn)返回 false，這樣，此映射的行為將類(lèi)似于正常映射，即永遠(yuǎn)不能移除最舊的元素。
我們會(huì)在后面的文章中詳細(xì)介紹關(guān)于如何用 LinkedHashMap 構(gòu)建 LRU 緩存。
其實(shí) LinkedHashMap 幾乎和 HashMap 一樣：從技術(shù)上來(lái)說(shuō)，不同的是它定義了一個(gè) Entry<K,V> header，這個(gè) header 不是放在 Table 里，它是額外獨(dú)立出來(lái)的。LinkedHashMap 通過(guò)繼承 hashMap 中的 Entry<K,V>,并添加兩個(gè)屬性 Entry<K,V> before,after,和 header 結(jié)合起來(lái)組成一個(gè)雙向鏈表，來(lái)實(shí)現(xiàn)按插入順序或訪問(wèn)順序排序。
在寫(xiě)關(guān)于 LinkedHashMap 的過(guò)程中，記起來(lái)之前面試的過(guò)程中遇到的一個(gè)問(wèn)題，也是問(wèn)我 Map 的哪種實(shí)現(xiàn)可以做到按照插入順序進(jìn)行迭代？當(dāng)時(shí)腦子是突然短路的，但現(xiàn)在想想，也只能怪自己對(duì)這個(gè)知識(shí)點(diǎn)還是掌握的不夠扎實(shí)，所以又從頭認(rèn)真的把代碼看了一遍。
不過(guò)，我的建議是，大家首先首先需要記住的是：LinkedHashMap 能夠做到按照插入順序或者訪問(wèn)順序進(jìn)行迭代，這樣在我們以后的開(kāi)發(fā)中遇到相似的問(wèn)題，才能想到用 LinkedHashMap 來(lái)解決，否則就算對(duì)其內(nèi)部結(jié)構(gòu)非常了解，不去使用也是沒(méi)有什么用的。
我們學(xué)習(xí)的目的是為了更好的應(yīng)用。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多