主要內(nèi)容：
- LinkedHashMap數(shù)據(jù)結(jié)構(gòu)
- 繼承關(guān)系、關(guān)鍵屬性、構(gòu)造函數(shù)
- 插入、查找元素
- 擴容
- 迭代器
- 與HashMap比較
LinkedHashMap概述
- 有序的Map接口實現(xiàn)，有序指元素可以按照訪問順序或插入順序迭代。內(nèi)部維護了一個雙向循環(huán)鏈表來實現(xiàn)有序。
- 非線程安全。
LinkedHashMap數(shù)據(jù)結(jié)構(gòu)
因為LinkedHashMap繼承HashMap，基本操作與HashMap相似，通過重寫相關(guān)方法來實現(xiàn)自己的特性。LinkedHashMap底層還實現(xiàn)了一個雙向循環(huán)鏈表，所以重新定義了數(shù)組中保存的Entry對象。
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);
}
//改變前后元素的引用關(guān)系
private void remove() {
before.after = after;
after.before = before;
}
//將節(jié)點插入到已存在的節(jié)點之前
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* 重寫了HashMap 的recordAccess方法；
* 如果是按照訪問順序排序，將節(jié)點移到鏈表尾部(頭節(jié)點之前)，否則不做操作
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
/**
* LinkedHashMap中沒有重寫remove(Object key)方法，
* 重寫了HashMap中的recordRemoval方法，在HashMap中為空方法
*/
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
LinkedHashMap的Entry包含三個指針，前后元素的引用指向雙向鏈表的連接外，還有next指針來解決hash沖突。recordAccess(HashMap<K,V> m)方法在LinkedHashMap的get方法以及繼承HashMap 的put方法中調(diào)用，如果是按照訪問順序排序，將當(dāng)前訪問的節(jié)點放入鏈表尾部，所以最少訪問的數(shù)據(jù)在鏈表頭部。
源碼分析
繼承關(guān)系
LinkedHashMap繼承關(guān)系.png
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
- 繼承HashMap，基本操作與HashMap類似。
關(guān)鍵屬性
//雙向循環(huán)鏈表的頭節(jié)點
private transient Entry<K,V> header;
//true表示按照訪問順序排序，false為按照插入順序
private final boolean accessOrder;
構(gòu)造函數(shù)
//使用指定的容量以及加載因子生成一個空的LinkedHashMap，默認按插入順序排序
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定容量大小生成一個空的LinkedHashMap，默認負載因子0.75以及按照插入順序排序
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//生成一個空的LinkedHashMap，默認容量大小16、負載因子0.75以及按照插入順序排序
public LinkedHashMap() {
super();
accessOrder = false;
}
//根據(jù)指定的map生成一個新的LinkedHashMap，默認負載因子0.75以及按插入順序排序
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
//指定容量大小、負載因子以及排序順序生成一個空的LinkedHashMap
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
所有構(gòu)造方法都通過父類HashMap的構(gòu)造函數(shù)來創(chuàng)建LinkedHashMap的。從這幾個方法源碼觀察，發(fā)現(xiàn)沒有初始化header的代碼，那它又是從哪里初始化的？？觀察HashMap 的構(gòu)造函數(shù)可以發(fā)現(xiàn)有個沒有實現(xiàn)的init()方法(這是鉤子方法)，子類LinkedHashMap實現(xiàn)了這個方法初始化雙向鏈表的頭節(jié)點。
/**
* 覆蓋HashMap的init方法，構(gòu)造方法、readObject以及clone方法均有調(diào)用該方法
* 生成頭節(jié)點并初始化雙向循環(huán)鏈表
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);//hash值－1，key、value和下一個元素引用均為null
header.before = header.after = header;
}
插入
LinkedHashMap沒有重寫put方法，重寫了addEntry和createEntry方法，且實現(xiàn)了Entry對象的recordAccess方法。
//創(chuàng)建節(jié)點插入到LinkedHashMap中。有必要的話刪除最少訪問的節(jié)點
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
Entry<K,V> eldest = header.after;//鏈表頭部的第一個節(jié)點，即最少訪問的節(jié)點或最先插入的節(jié)點
if (removeEldestEntry(eldest)) {//有必要的(如容量不夠，這里默認為false)刪除該節(jié)點
removeEntryForKey(eldest.key);
}
}
//創(chuàng)建節(jié)點，新鍵值對分別放在桶數(shù)組和鏈表尾部
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++;
}
可以繼承LinkedHashMap，并重寫removeEldestEntry方法自動刪除鏈表最少訪問的鍵值對或者最先插入的鍵值對，可以用來做緩存。
get方法
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);//若LinkedHashMap按訪問順序排序，將訪問的當(dāng)前節(jié)點移到鏈表尾部
return e.value;
}
擴容
LinkedHashMap沒有重寫resize方法，重寫了HashMap的transfer方法。
//獲取對象采用遍歷雙向循環(huán)鏈表的方式，而不是原先的雙重循環(huán)，性能更優(yōu)
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍歷舊map的鍵值對
for (Entry<K,V> e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
//根據(jù)新的容量大小重新計算索引
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
迭代器
LinkedHashMap自定義迭代器，通過遍歷雙向循環(huán)鏈表來完成迭代，遍歷時間與鍵值對個數(shù)成正比。
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
int expectedModCount = modCount;//fail-fast機制
public boolean hasNext() {//雙向鏈表結(jié)束標志
return nextEntry != header;
}
public void remove() {//移除節(jié)點
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() {//下一個節(jié)點
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
private class KeyIterator extends LinkedHashIterator<K> {//key迭代器
public K next() { return nextEntry().getKey(); }
}
private class ValueIterator extends LinkedHashIterator<V> {//value迭代器
public V next() { return nextEntry().value; }
}
private class EntryIterator extends
LinkedHashIterator<Map.Entry<K,V>> {//鍵值對迭代器
public Map.Entry<K,V> next() { return nextEntry(); }
}
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
與HashMap比較
- 相同：都是散列表的實現(xiàn)；繼承自HashMap，具有大部分它的特性。
- 不同：LinkedListMap內(nèi)部維護了一個雙向循環(huán)鏈表，可以按照訪問順序LRU或插入順序排序，迭代操作是遍歷hash表，而是遍歷雙向循環(huán)鏈表。LinkedHashMap=HashMap+循環(huán)鏈表。
