LinkedHashMap 簡(jiǎn)介
HashMap 是 Java 中非常常見(jiàn)的集合，但是 HashMap 有一個(gè)問(wèn)題，就是迭代HashMap的順序并不是HashMap放置的順序。在一些應(yīng)用場(chǎng)景中，我們是希望獲得有序的 Map 的。
正是基于此，就有了 LinkedHashMap。LinkedHashMap 繼承了 HashMap，在 HashMap 的基礎(chǔ)上，通過(guò)內(nèi)部維護(hù)一個(gè)雙向鏈表，能夠保證元素迭代的順序。其順序可以是插入順序或者是訪問(wèn)順序。
在這里對(duì)源碼的分析，就不再重復(fù) HashMap 中已存在的內(nèi)容，只著重于 LinkedHashMap 中獨(dú)有的部分。
LinkedHashMap 中新增的屬性
LinkedHashMap 中加入了兩個(gè)屬性：
- header： 雙向鏈表中的頭
- accessOrder： 訪問(wèn)順序，默認(rèn)為 false，即插入順序。
LinkedHashMap 內(nèi)部鍵值對(duì)類 Entry
LinkedHashMap 的內(nèi)部類 Entry 實(shí)現(xiàn)。
Entry 繼承了 HashMap 的 Entry，加入了關(guān)于雙向鏈表的屬性和常用方法。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
// 從雙向鏈表中刪除
private void remove() {
before.after = after;
after.before = before;
}
// 在指定節(jié)點(diǎn)前插入節(jié)點(diǎn)
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
// 若為訪問(wèn)順序，則移動(dòng)節(jié)點(diǎn)到鏈尾
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
// 刪除
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
LinkedHashMap 重寫(xiě)的方法
構(gòu)造方法
構(gòu)造方法調(diào)用了 HashMap 的方法，加入了初始化 accessOrder 為 false。以及重寫(xiě)了 init 方法。
init 方法是在 HashMap 構(gòu)造方法中會(huì)調(diào)用到的方法。原來(lái)為空實(shí)現(xiàn)，這里加入了初始化雙向鏈表的操作。
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
添加元素時(shí)對(duì)雙向鏈表的維護(hù)
addEntry 方法
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
createEntry 方法
創(chuàng)建鍵值對(duì)放入桶中，在雙向鏈表鏈尾中加入該節(jié)點(diǎn)。可以看到這里所有的插入操作，都是把元素插入到鏈表的頭部，因此只要遍歷 after，即為插入排序迭代。
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
transfer 方法
transfer 方法只有 resize 方法會(huì)調(diào)用到，也就是 Map 動(dòng)態(tài)擴(kuò)充時(shí)。
這里就是遍歷雙向鏈表，用頭插法把鍵值對(duì)插入到桶中。
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
訪問(wèn)順序的實(shí)現(xiàn)原理
在調(diào)用 get 方法和添加元素時(shí)鍵值已存在時(shí)，均會(huì)調(diào)用 Entry 的 recordAccess 方法?？梢钥吹剑魹樵L問(wèn)順序時(shí)， recordAccess 會(huì)把該元素移動(dòng)到鏈表的頭部。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
基于 LinkedHashMap 實(shí)現(xiàn) FIFO 和 LRU
FIFO（First In First out）： 先見(jiàn)先出，淘汰最先近來(lái)的頁(yè)面，新進(jìn)來(lái)的頁(yè)面最遲被淘汰，完全符合隊(duì)列。
LRU（Least recently used）: 最近最少使用，淘汰最近不使用的頁(yè)面。
在前面的 addEntry 方法中，這里還調(diào)用了一個(gè)判斷方法 removeEldestEntry，若為真，則刪除鏈尾元素。我們可以利用此方法來(lái)實(shí)現(xiàn) FIFO 和 LRU。
重寫(xiě) removeEldestEntry 方法，若超過(guò)長(zhǎng)度則刪除鏈尾元素。
當(dāng)為訪問(wèn)順序時(shí)，由于長(zhǎng)訪問(wèn)的都被移動(dòng)到了鏈頭位置，因此最少訪問(wèn)的元素在鏈表尾部。所以實(shí)現(xiàn)了 LRU。
為插入順序時(shí)，最早插入的元素被移動(dòng)到了鏈尾位置，刪除鏈尾元素，則實(shí)現(xiàn)了 FIFO。
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
總結(jié)
LinkedHashMap 是在 HashMap 的基礎(chǔ)上，加入了一個(gè)雙向鏈表，所有的鍵值對(duì)元素都在這條雙向鏈表上。通過(guò)維護(hù)雙向鏈表，實(shí)現(xiàn)了順序迭代。
