LinkedHashMap是HashMap的子類耐亏，在擁有HashMap功能之外可以保存元素插入順序焕毫，使得元素遍歷順序與元素插入順序相同。同時(shí)LinkedHashMap還可以根據(jù)元素訪問的時(shí)間先后順序來遍歷元素，Lru(Least recently used)算法中就是應(yīng)用了LinkdHashMap這一性質(zhì)哲银。那么這些功能具體是如何實(shí)現(xiàn)的莱没，只能通過解析源碼來揭秘了初肉。
LinkedHashMap構(gòu)造函數(shù)
構(gòu)造函數(shù)除了正常調(diào)用父類HashMap的構(gòu)造函數(shù)之外，還初始化了accessOrder為false.accessOrder為false時(shí)饰躲，表明遍歷元素是按照插入順序來訪問牙咏，即遍歷輸出順序和當(dāng)初元素插入順序相同；accessOrder為true時(shí)嘹裂，表明遍歷元素順序是根據(jù)訪問元素時(shí)間先后順序來遍歷元素妄壶，即最近訪問的元素最后輸出。具體會(huì)在下文解釋寄狼。
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
在HashMap構(gòu)造函數(shù)有個(gè)init函數(shù)沒有實(shí)現(xiàn)丁寄，在LinkedHashMap中實(shí)現(xiàn)了〔蠢ⅲ可以看出這個(gè)函數(shù)new了一個(gè)LinkedHashMapEntry類型的header節(jié)點(diǎn)伊磺，LinkedHashMapEntry繼承了HashMapEntry,增加了before和after指針。這個(gè)before和after和next有什么區(qū)別删咱？從第二行代碼只能看出是建立了一個(gè)環(huán)形雙向鏈表屑埋。要想知道有什么區(qū)別，需要繼續(xù)挖掘痰滋。
@Override
void init() {
header = new LinkedHashMapEntry<>(-1, null, null, null);
header.before = header.after = header;
}
LinkedHashMap的put和擴(kuò)容
LinkedHashMap沒有實(shí)現(xiàn)put函數(shù)雀彼，還是調(diào)用HashMap的put函數(shù)壤蚜。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
其中recordAccess是HashMapEntry的成員函數(shù)，在HashMap中是個(gè)空函數(shù)徊哑，具體實(shí)現(xiàn)在LInkedHashMap中袜刷。可以猜想這個(gè)函數(shù)與LInkedHashMap的順序存儲有關(guān)莺丑。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//首先判斷是否為當(dāng)前是否為訪問順序模式著蟹。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
// 這里其實(shí)是刪除雙鏈表單節(jié)點(diǎn)的操作，
private void remove() {
//當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的after指針指向當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)梢莽。
before.after = after;
// before指針指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)萧豆。
after.before = before;
}
// 將當(dāng)前節(jié)點(diǎn)插入到環(huán)形鏈表的頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，其實(shí)也就是雙鏈表的尾部
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
因此在put操作時(shí)昏名，如果該key的元素存在涮雷，recordAccess會(huì)通過刪除節(jié)點(diǎn)并將該節(jié)點(diǎn)重新插入到雙鏈表的尾部。這樣就可以解釋第一節(jié)中的疑問轻局，在遍歷時(shí)最近訪問的元素會(huì)最后輸出洪鸭，就是因?yàn)槊看蝡ut操作會(huì)把節(jié)點(diǎn)重新放置到雙鏈表尾部。
LinkedHashMap重寫了addEntry仑扑，但是removeEldestEntry默認(rèn)返回false览爵。其實(shí)和HashMap的addEntry一樣。同時(shí)重寫了createEntry().相比于HashMap镇饮，不同在于多調(diào)用了addBefore函數(shù)蜓竹。在上面已經(jīng)分析了，是將該節(jié)點(diǎn)移動(dòng)到雙鏈表的尾部储藐。也就是LinkedHashMap除了要維護(hù)一個(gè)數(shù)組加鏈表俱济，還要維護(hù)一個(gè)雙鏈表。
void addEntry(int hash, K key, V value, int bucketIndex) {
LinkedHashMapEntry<K,V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
if (removeEldest) {
removeEntryForKey(eldest.key);
}
}
super.addEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
LinkedHashMap的擴(kuò)容也是不同的钙勃，重寫了resize中的transfer函數(shù)姨蝴。HashMap中是通過遍歷每個(gè)鏈表來將舊元素拷貝到新的數(shù)組中，而LinkedHashMap由于有雙向鏈表來維護(hù)所有元素肺缕，因此直接遍歷雙向鏈表來拷貝舊元素左医。從遍歷的效率來說，遍歷雙向鏈表的效率要高于遍歷table同木，因?yàn)楸闅v雙向鏈表是N次（N為元素個(gè)數(shù)）浮梢；而遍歷table是N+table的空余個(gè)數(shù)（N為元素個(gè)數(shù)）。
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
