Java集合(一) —— Collection源碼分析
Java集合(二) —— ArrayList源碼分析
Java集合(三) —— LinkedList源碼分析
Java集合(四) —— PriorityQueue源碼分析
Java集合(五) —— HashSet源碼分析
Java集合(六) —— LinkedHashSet源碼分析
Java集合(七) —— TreeSet源碼分析
Java集合(八) —— HashMap源碼分析
Java集合(九) —— LinkedHashMap源碼分析
Java集合(十) —— TreeMap源碼分析
1.總結(jié)
1.LinkedHashMap繼承自HashMap，所以HashMap有的特性LinkedHashMap都有，比如數(shù)據(jù)結(jié)構(gòu)為數(shù)組+鏈表+紅黑樹荷愕，默認(rèn)容量為16辅辩，負(fù)載因子為0.75等(HashMap源碼分析)。
2.LinkedHashMap使用雙向鏈表維持?jǐn)?shù)據(jù)的插入順序或訪問順序(默認(rèn)是以插入順序排序)夭问。
3.當(dāng)以訪問順序排序時(shí)，被訪問的節(jié)點(diǎn)都要從當(dāng)前位置移到鏈表尾部。
2.繼承關(guān)系圖
3.源碼分析
3.1成員變量分析
// 雙向鏈表的頭結(jié)點(diǎn)
transient LinkedHashMap.Entry<K,V> head;
// 雙向鏈表的尾結(jié)點(diǎn)
transient LinkedHashMap.Entry<K,V> tail;
// 排序方式旅敷，false：插入順序；true：訪問順序
final boolean accessOrder;
3.2構(gòu)造方法分析
/**
* 指定初始化容量和負(fù)載因子
* accessOrder：默認(rèn)都為false颤霎，表示以插入順序排序
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 指定初始化容量
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 默認(rèn)構(gòu)造
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 用已存在的map初始化LinkedHashMap
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder; // 指定是否以訪問順序排序
}
3.3常用方法分析
1.put方法
調(diào)用的就是HashMap的put方法媳谁，不同的是LinkedHashMap重寫了newNode方法，實(shí)現(xiàn)了afterNodeAccess和afterNodeInsertion方法
/**
* 新建節(jié)點(diǎn)友酱，新節(jié)點(diǎn)接在雙向鏈表尾部
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 將節(jié)點(diǎn)接在雙向鏈表尾部
linkNodeLast(p);
return p;
}
/**
* 將節(jié)點(diǎn)連接到鏈表尾部
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
// 將尾結(jié)點(diǎn)指向p
tail = p;
// 如果last為null晴音，表示鏈表還沒有建立
if (last == null)
head = p;
else {
// 將新節(jié)點(diǎn)接到鏈表尾部，新節(jié)點(diǎn)的前向指針指向last缔杉，last的后繼指針指向新節(jié)點(diǎn)
p.before = last;
last.after = p;
}
}
再看看實(shí)現(xiàn)的兩個(gè)方法：
- afterNodeAccess方法
void afterNodeAccess(Node<K,V> e) { // move node to last 將節(jié)點(diǎn)移到鏈表最后
LinkedHashMap.Entry<K,V> last;
// 當(dāng)以訪問順序排序锤躁，且e不是尾結(jié)點(diǎn)時(shí)
if (accessOrder && (last = tail) != e) {
// p => e; b => p的前驅(qū); a => p的后繼
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null) // 表示p原先為頭節(jié)點(diǎn)
// 將p移到鏈表尾部后，p的后繼節(jié)點(diǎn)a成為頭結(jié)點(diǎn)
head = a;
else
// 否則將b的后繼指向a（此時(shí)p從鏈表中刪除或详，將斷開的鏈表重新連接起來）
b.after = a;
if (a != null)
// a不為null系羞，則a的前驅(qū)指向b
a.before = b;
else
// 否則b成為最后一個(gè)節(jié)點(diǎn)
last = b;
if (last == null)
// 鏈表只有p節(jié)點(diǎn)郭计，將頭結(jié)點(diǎn)指向p
head = p;
else {
// 否則將p節(jié)點(diǎn)連接到鏈表尾部
p.before = last;
last.after = p;
}
// 尾結(jié)點(diǎn)指向p
tail = p;
++modCount;
}
}
- afterNodeInsertion方法
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 刪除節(jié)點(diǎn)
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
從源碼可以看到，需要同時(shí)滿足三個(gè)條件才會(huì)才會(huì)進(jìn)入if語句
1.evict為true
2.first不為null
3.removeEldestEntry(first)方法返回true
然而默認(rèn)的removeEldestEntry(first)始終返回false觉啊，也就是說默認(rèn)不會(huì)刪除節(jié)點(diǎn)拣宏。removeEldestEntry(first)用于定義刪除最老元素的規(guī)則。
2.get方法
public V get(Object key) {
Node<K,V> e;
// getNode()方法為查找節(jié)點(diǎn)的具體實(shí)現(xiàn)杠人，在HashMap中已經(jīng)分析過勋乾，這里不再說明
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果accessOrder為true，表示以訪問順序排序
if (accessOrder)
// 調(diào)整鏈表嗡善，將訪問的節(jié)點(diǎn)移到鏈表尾部
afterNodeAccess(e);
return e.value;
}
3.remove方法
調(diào)用的就是HashMAp的remove方法辑莫，不同的是LinkedHashMap實(shí)現(xiàn)了afterNodeRemoval方法。
/**
* e：待刪除節(jié)點(diǎn)
*/
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
afterNodeRemoval()實(shí)現(xiàn)從雙向鏈表中刪除節(jié)點(diǎn)罩引，并將斷開的鏈表重新連接起來各吨。
4.entrySet，keySet袁铐，values方法
entrySet揭蜒，keySet，values與HashMap中的這三個(gè)方法大同小異剔桨，其中entrySet和keySet通過迭代器將鍵值對/鍵映射到entrySet和keySet上屉更，values是一個(gè)Collection集合：
/**
* 跟HashMap的實(shí)現(xiàn)是一樣的
*/
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new LinkedValues();
values = vs;
}
return vs;
}
