概述
文章的内容基于JDK1.7進行分析,之是以選用這個版本,是因為1.8的有些類做了改動,增加了閱讀的難度,雖然是1.7,但是對于1.8做了重大改動的内容,文章也會進行說明。
LinkedHashMap,見名知義,帶連結清單的HashMap, 是以LinkedHashMap是有序,LinkedHashMap作為HashMap的擴充,它改變了HashMap無序的特征。它使用了一個雙向的連結清單來會維護key-value對的次序,該連結清單維護了map的疊代順序,該疊代順序和key-value對的插入順序保持一緻。LinkedHashMap重寫了父類的一些方法,這些方法也會在下面的文章中進行說明。
資料結構繼承關系java.lang.Object
java.util.AbstractMap
java.util.HashMap
java.util.LinkedHashMap
從上面的內建關系中看出,LinkedHashMap內建了HashMap類,是以便擁有了HashMap開放的所有功能,而LinkedList在所有功能的基礎上又進行了更新,添加了記住元素添加順序的職責。實作接口Serializable, Cloneable, Map
LinkedHashMap 可序列化,可以被克隆 ,實作了Map接口基本屬性private transient Entry header; //雙向連結清單的頭節點private final boolean accessOrder; //排序的規則,false按插入順序排序,true通路順序排序
重要方法深度解析構造方法//LinkedHashMap的構造方法,都是通過調用父類的構造方法來實作,大部分accessOrder預設為falsepublic LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor);
accessOrder = false;
}public LinkedHashMap(int initialCapacity) { super(initialCapacity);
accessOrder = false;
}public LinkedHashMap() { super();
accessOrder = false;
}public LinkedHashMap(Map extends K, ? extends V> m) { super(m);
accessOrder = false;
}public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;
}
上面是LinkedHashMap的構造方法,通過傳入初始化參數和代碼看出,LinkedHashMap的構造方法和父類的構造方法,是一一對應的。也是通過super()關鍵字來調用父類的構造方法來進行初始化,唯一的不同是最後一個構造方法,提供了AccessOrder參數,用來指定LinkedHashMap的排序方式,accessOrder =false -> 插入順序進行排序 , accessOrder = true -> 通路順序進行排序。
put()方法
LinkedHashMap并沒有重寫父類的put()方法,說明調用put方法時實際上調用的是父類的put方法。
get()方法public V get(Object key) {
Entry e = (Entry)getEntry(key); //調用父類的getEntry()方法
if (e == null) return null;
e.recordAccess(this); //判斷排序方式,如果accessOrder = true , 删除目前e節點
return e.value;
}
remove()
LinkedHashMap并沒有重寫父類的remove()方法,說明調用remove方法時實際上調用的是父類的remove()方法。
源碼解析Entry定義private static class Entry extends HashMap.Entry { //定義Entry類型的兩個變量,或者稱之為前後的兩個指針
Entry before, after; //構造方法與HashMap的沒有差別,也是調用父類的Entry構造方法
Entry(int hash, K key, V value, HashMap.Entry next) { super(hash, key, value, next);
} //删除
private void remove() {
before.after = after;
after.before = before;
} //插入節點到指定的節點之前
private void addBefore(Entry existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
} //方法重寫,HashMap中為空
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m; if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
} //方法重寫 ,HashMap中方法為空
void recordRemoval(HashMap m) {
remove();
}
}public class LinkedHashMap extends HashMap implements Map{ //可序列化版本号
private static final long serialVersionUID = 3801124242820219131L; //雙向連結清單的頭指針
private transient Entry header; //雙向連結清單的排序方法,false 插入順序排序,true通路順序排序
private final boolean accessOrder; //構造方法,指定初始大小,指定負載因子
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor);
accessOrder = false;
} //構造方法,指定初始容量
public LinkedHashMap(int initialCapacity) { super(initialCapacity);
accessOrder = false;
} //無參構造方法k,采用預設參數
public LinkedHashMap() { super();
accessOrder = false;
} //将指定的m集合轉化為LinkedHashmap存儲
public LinkedHashMap(Map extends K, ? extends V> m) { super(m);
accessOrder = false;
} //構造方法,指定初始容量,負載因子和排序方式
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;
} //重寫父類init方法,init方法在父類構造函數被調用,初始化雙向連結清單
//header的前驅和後繼都是指向它自己
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
} //重寫父類的transfer方法,在HashMap執行擴容操作時被調用,HashMap中的是通過周遊Entry[]數組的方式來實作資料的拷貝複制,重寫後是通過周遊雙向連結清單的方式來進行資料的複制。周遊雙向連結清單的方式效率上更高一些
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry 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;
}
} //重寫父類的containsValue, 由周遊數組的方式修改為周遊清單的方式
public boolean containsValue(Object value) { // Overridden to take advantage of faster iterator
if (value==null) { for (Entry e = header.after; e != header; e = e.after) if (e.value==null) return true;
} else { for (Entry e = header.after; e != header; e = e.after) if (value.equals(e.value)) return true;
} return false;
} //重寫父類的get方法
public V get(Object key) {
Entry e = (Entry)getEntry(key); //傳回實體
if (e == null) return null;
e.recordAccess(this); //如果是通路順序排序,則将e移動到連結清單的末尾處
return e.value;
} //清除集合
public void clear() { super.clear();
header.before = header.after = header;
} //内部類實作了疊代方法
private abstract class LinkedHashIterator implements Iterator {
Entry nextEntry = header.after;
Entry lastReturned = null;
int expectedModCount = modCount; public boolean hasNext() { return nextEntry != 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 nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (nextEntry == header) throw new NoSuchElementException();
Entry e = lastReturned = nextEntry;
nextEntry = e.after; return e;
}
} private class KeyIterator extends LinkedHashIterator { public K next() { return nextEntry().getKey(); }
} private class ValueIterator extends LinkedHashIterator { public V next() { return nextEntry().value; }
} private class EntryIterator extends LinkedHashIterator> { public Map.Entry next() { return nextEntry(); }
} // These Overrides alter the behavior of superclass view iterator() methods
Iterator newKeyIterator() { return new KeyIterator(); } Iterator newValueIterator() { return new ValueIterator(); }
Iterator> newEntryIterator() { return new EntryIterator(); } //重寫父類的addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) { super.addEntry(hash, key, value, bucketIndex);
Entry eldest = header.after; if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
} //重寫createEntry方法
//執行兩步操作:
// 1. 添加到table數組中, 2 . 插入到雙向連結清單中
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry old = table[bucketIndex];
Entry e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
} protected boolean removeEldestEntry(Map.Entry eldest) { return false;
}
}
下面詳細的分析一下LinkedHashMap中操作的實作:HashMap h = new LinkedHashMap();
h.put("張三", 18);
上面是簡短的兩句代碼,來看一下到底包含了何種的操作。
圖解LinkedHashMap的put操作.png
上面的圖檔已經描述的很清楚了,在此不再添加文字的表述。
關于删除方法,感興趣的可以自行研究。
總結
LinkedHashMap繼承了HashMap類,重寫了部分方法,在HashMap中一些空的實作,LinkedHashMap都做了實作,擴充了HashMap類的功能,LinkedHashMap可以儲存元素的插入順序,順序有兩種方式一種是按照插入順序排序,一種按照通路做排序。預設以插入順序排序,性能比HashMap略低,線程也是不安全的。
至此,Java集合的源碼系列就分析完了,像HashTable,stack等集合從開發者的角度上已經不建議在使用,因為已經是比較古老的類,有了更好類做了替代。
作者:起個名忒難
連結:https://www.jianshu.com/p/daf16e703049