LinkHashMap 簡(jiǎn)介
LinkHashMap 繼承自 HashMap 同時(shí)也實(shí)現(xiàn)了 Map 接口。所以 LinkHashMap 的方法與 HashMap 中的方法類似，我們知道 HashMap 的存儲(chǔ)的數(shù)據(jù)是無(wú)序的，而 LinkHashMap 則在 HashMap 的基礎(chǔ)上實(shí)現(xiàn)了有序的數(shù)據(jù)存儲(chǔ)，本文就主要查看源碼看看 LinkHashMap 是如何實(shí)現(xiàn)有序的存儲(chǔ)方式的；
如果對(duì)于 HashMap 的源碼不了解的，建議先看 HashMap 的源碼分析
)
LinkHashMap 的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)
我們知道 HashMap 在 JDK1.7 上的數(shù)據(jù)是基于數(shù)組和鏈表結(jié)構(gòu)進(jìn)行存儲(chǔ)的，而 LinkHashMap 在此基礎(chǔ)上增加了鏈表的雙向存儲(chǔ)結(jié)構(gòu)，先看下大致的示意圖
LinkHashMap 維護(hù)的 Entry 數(shù)據(jù)包含 before、hash、key、value、next、after 值，相對(duì)與 HashMap.Entry 多了 before 和 after 的指向，從而構(gòu)成雙向鏈表；
LinkHashMap 分析
LinkHashMap 在使用方法上和 HashMap 基本一致：
LinkedHashMap<String, Integer> hss = new LinkedHashMap<>();
hss.put("aaa", 1);
hss.put("bbb", 2);
hss.put("aaa", 3);
hss.get("aaa");
hss.remove("aaa");
for(Map.Entry<String, Integer> entry : hss.entrySet()){
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
Iterator<Map.Entry<String, Integer>> entries = hss.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<String, Integer> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
接下來(lái)繼續(xù)查看 LinkHashMap 對(duì)數(shù)據(jù)的相關(guān)操作，是如何能夠做到有序地存取數(shù)據(jù)？
LinkHashMap 的構(gòu)造方法：
public LinkedHashMap() {
super();
accessOrder = false;
}
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
LinkHashMap 在調(diào)用了 HashMap 的構(gòu)造方法后，設(shè)置了一個(gè) accessOrder 為 false，根據(jù)意思猜想這個(gè)和訪問(wèn)順序有關(guān)，此處先放著不管，后面會(huì)進(jìn)行詳細(xì)介紹。同時(shí) LinkHashMap 重寫了 init 方法，創(chuàng)建了一個(gè) header 的 節(jié)點(diǎn) ，這里的 Entry 是 LinkHashMap 的內(nèi)部類，和 HashMap 中的 Entry 有所區(qū)別；
LinkHashMap 的 put 方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
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;
}
LinkHashMap 的 put 方法其實(shí)就是調(diào)用了 HashMap 的 put 方法，前面邏輯和 HashMap 一致，直到調(diào)用到 addEntry 方法，LinkHashMap 進(jìn)行了重寫；
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);
}
}
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++;
}
addEntry 方法依然會(huì)調(diào)用到 HashMap 的 addEntry 方法，這里也可以再回顧下 HashMap 的 addEntry 方法；
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {// 是否需要擴(kuò)容處理
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);// 創(chuàng)建數(shù)據(jù)節(jié)點(diǎn)
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
HashMap 的 addEntry 最終會(huì)調(diào)用 createEntry 方法，而 LinkHashMap 同時(shí)也重寫了 createEntry 方法，所以這里重點(diǎn)分析就在 LinkHashMap 中的 addEntry 和 createEntry 方法了；
首先，和 HashMap 一樣對(duì)數(shù)據(jù)擴(kuò)容判斷，之后就直接調(diào)用了 createEntry 方法；
createEntry 方法中 LinkHashMap 比 HashMap 多一步，e.addBefore(header)
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
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;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
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();
}
}
LinkHashMap 的 Entry 為自身的內(nèi)部類，前面在初始化的方法中提到會(huì)創(chuàng)建一個(gè) header Entry；
LinkHashMap 的 addBefore 方法其過(guò)程就是雙向鏈表指向的不斷交換過(guò)程，下圖演示 LinkHashMap 在依次添加 Num1、 Num2、 Num3 的過(guò)程中鏈表指向不斷改變的過(guò)程；
未進(jìn)行添加元素前：
看到 Header 元素的 before 和 after 都指向自己；
接下來(lái)添加 Num1 ：
Header 和 Num1 數(shù)據(jù)的 before 和 after 相互進(jìn)行鏈接指向；
繼續(xù)添加 Num2：
此時(shí)，header 的 before 指向 Num2，同時(shí) Num2 的 before 指向 Num1， Num1 的 before 指向 Header，這里的 before 就像是一個(gè)倒序的循環(huán)，Num2 -> Num1;而 after 指向的情況正好相反，Num1 -> Num2, 這正好符合我們加入的順序；
最后加入 Num3 ，假設(shè) Num3 的數(shù)組索引位置和 Num1 相同，同樣遵循 HashMap 的插入規(guī)則：
這里 header 和 after 的指向和上述情況一致，只不過(guò) Num3 有個(gè) next 的指向?yàn)?Num1；
看完 LinkHashMap 的插入操作，可以發(fā)現(xiàn)通過(guò)雙向的鏈表 LinkHashMap 其實(shí)已經(jīng)完成了插入順序的記錄過(guò)程；仔細(xì)看從 header 的 after 開(kāi)始訪問(wèn)數(shù)據(jù) ，依次是 Num1、Num2、Num3 和插入順序一致；當(dāng)再次訪問(wèn)到 header 節(jié)點(diǎn)的時(shí)候即數(shù)據(jù)訪問(wèn)完成；
需要注意的是，上述過(guò)程在完成添加操作之后，還會(huì)做一個(gè) removeEldestEntry 操作， 刪除第一個(gè)元素；默認(rèn)返回 false 不執(zhí)行判斷體，可供繼承者使用；
LinkHashMap 的 get 方法：
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
調(diào)用 HashMap 的 getEntry 方法，和 HashMap 處理基本一致；
LinkHashMap 的 remove 方法：
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
同樣調(diào)用 HashMap 的 removeEntryForKey 方法移除相應(yīng)的數(shù)據(jù)即可；
LinkHashMap 的遍歷
通過(guò) HashMap 的介紹我們可以知道，HashMap 是通過(guò) HashIterator 實(shí)現(xiàn) Iterator 來(lái)完成的，前面 LinkHashMap 通過(guò)雙向鏈表已經(jīng)記錄了數(shù)據(jù)的插入順序，接下來(lái)看看 LinkHashMap 如何去按順序取出數(shù)據(jù)？
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after; // 訪問(wèn)開(kāi)始點(diǎn)
Entry<K,V> lastReturned = null;
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;// 再次指向 header
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;// 移到下一個(gè)點(diǎn)
return e;
}
}
LinkHashMap 內(nèi)部維護(hù)了自身的 Entry 類，Entry 類中維護(hù)的 EntryIterator 類集成自 LinkedHashIterator；
LinkedHashIterator 從 header.after 開(kāi)始訪問(wèn)，以 after 進(jìn)行訪問(wèn)點(diǎn)移動(dòng)，直到節(jié)點(diǎn)指向 header 結(jié)束；以上述 Num1、Num2、Num3的案例來(lái)看，依次取出數(shù)據(jù)是 Num1、Num2、Num3 ，和存放的數(shù)據(jù)一致，從而實(shí)現(xiàn)了有序的排序；
在這里 modCount 和 expectedModCount 的判斷過(guò)程以及內(nèi)部操作無(wú)同步機(jī)制，表明 LinkHashMap 是非線程安全的集合類（同 HashMap）。
LinkHashMap 的 accessOrder
最后，來(lái)看下 accessOrder 這里變量的意義。accessOrder 在 LinkHashMap 的初始化中默認(rèn)為 false，代表按照插入順序進(jìn)行排序。加入設(shè)置true 則代表訪問(wèn)順序進(jìn)行排序，具體可以搜索到 LinkHashMap 中的相關(guān)代碼：
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
LinkHashMap 中 recordAccess 方法會(huì)用到 accessOrder 這個(gè)變量，可以看到這個(gè)變量將當(dāng)前數(shù)據(jù)進(jìn)行刪除，addBefore 方法會(huì)將其插入到雙向鏈表最后一位。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
而 recordAccess 方法則會(huì)在 LinkHashMap get 數(shù)據(jù)的時(shí)候進(jìn)行調(diào)用。此時(shí)將訪問(wèn)的到的數(shù)據(jù)放到最末位。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {// 帶 accessOrder 賦值的構(gòu)造方法
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap<String, Integer> hss = new LinkedHashMap<>(16,0.75f,true);
hss.put("aaa", 1);
hss.put("bbb", 2);
hss.put("ccc", 3);
hss.get("aaa");
for(Map.Entry<String, Integer> entry : hss.entrySet()){
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
上述案例將 accessOrder 設(shè)置為 true ，最終遍歷到的順序?yàn)?2、 3、 1；
LinkHashMap 總結(jié)
最后，通過(guò)本篇文章對(duì) LinkHashMap 做一個(gè)簡(jiǎn)單總結(jié)：
1、LinkHashMap 是一個(gè)有序的集合類，可存儲(chǔ) null key；
2、LinkHashMap 是非線程安全的集合類；
3、LinkHashMap 采用了雙向鏈表保證數(shù)據(jù)的存儲(chǔ)順序；
4、LinkHashMap accessOrder 可以用來(lái)把最近訪問(wèn)的數(shù)據(jù)放在最后一位，這一點(diǎn)在實(shí)際相關(guān) LRU 數(shù)據(jù)緩存操作經(jīng)常用使用到；
