HashMap部分源碼集解
????????本文將主要分析HashMap的重點方法，包括put(), get(), resize()。并對其重點代碼進行解釋說明。
# 閱讀本文需具備基礎的知識：
??? 1. 了解Java基礎知識；
??? 2. 對HashMap有一定的了解并懂得HashMap中一些基本屬性的作用；
##?put?方法集解
public V put(K key, V value) {
//計算key的hash值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// Node數(shù)組非空判斷，為空則調用resize方法進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過(n - 1) & hash 的方式計算出key的位置，再對當前位置的元素進行非空判斷，為null則直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
else {
Node e; K k;
//判斷key是否存在，存在則下面邏輯選擇性覆蓋舊值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷是否為紅黑樹結構，是的話以紅黑樹的方式插入
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 鏈表的下一節(jié)點為null，將數(shù)據(jù)插入尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長度 >= 8 則轉變?yōu)榧t黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果鏈表中存在key值相等元素則跳出循環(huán)，在下面邏輯選擇性覆蓋舊值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果key已存在，則根據(jù)onlyIfAbsent選擇性用新值替換舊值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// HashMap線程安全的保障
++modCount;
// 當Node數(shù)組的長度大于擴容閾值時則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
##?put重點代碼發(fā)明
1.??為什么用(n - 1) & hash 的方式計算元素下標？
原因：(n - 1)?& hash == hash % n, 并且(n - 1)?& hash 的效率要高。(n為2的次冪)
解釋：
當n == 8 == 1000, hash == 59 == 111011時。
? (n?-?1)?&?hash?==?11?并且?111011?==?11?==?3，
???59?%?8?==?3
??根據(jù)位運算規(guī)則可知，二進制數(shù)中凡是低三位為0的數(shù)都可以被100整除，低三位的值即為余數(shù)；
利用位與運算，將高位置0，低三位置為原值，結果低三位的原值即為余數(shù)。
所以當n為2的次冪時，(n?-?1)?&?hash?即為?hash?%?n的值
2. putVal方法中onlyIfAbsent的意義及作用
onlyIfAbsent： ???? ????- 如果存在新key和舊key相同，是否用新值覆蓋舊值；???? ????- 如果為true，則新值不覆蓋舊值。false則進行覆蓋。
3. modCount的作用
記錄集合被修改的次數(shù)。 當操作HashMap時，發(fā)現(xiàn)modCount發(fā)生改變時進入快速失敗，拋出 ConcurrentModificati onException
##?resize?方法集解
final Node[] resize() {
Node[] oldTab = table;
// 獲取原哈希表容量；若原哈希表為null，則容量為0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 獲取原哈希表擴容門檻
int oldThr = threshold;
// 初始化新哈希表容量和新哈希表門檻為0
int newCap, newThr = 0;
// 如果原容量大于0，計算擴容后的容量及新的負載擴容門檻
if (oldCap > 0) {
//判斷原容量是否大于等于HashMap允許的容量最大值 - 2的30次冪
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果原容量大于等于允許的最大容量，則把HashMap的擴容門檻設置為Integer允許的最大值
threshold = Integer.MAX_VALUE;
//不再擴容，直接返回
return oldTab;
}
// 把原Node數(shù)組容量擴大為原來的2倍作為新Node數(shù)組的容量。
// 如果新Node數(shù)組的容量小于HashMap所允許的容量的最大值: 2的30次冪，并且原Node數(shù)組容量大于等于默認的初始化Node數(shù)組容量: 2的4次冪 -> 16，則計算新的擴容門檻
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新Node數(shù)組的擴容門檻為原Node數(shù)組的擴容門檻的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果原Node數(shù)組容量小于等于0并且原Node數(shù)組擴容門檻大于0，新Node數(shù)組容量為原Node數(shù)組擴容門檻大小
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 如果原Node數(shù)組容量小于等于0并且原Node數(shù)組的擴容門檻小于等于0，則初始化新Node數(shù)組容量為默認初始化容量：1 << 4；
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的擴容門檻等于0，則重新計算新的擴容門檻
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
({"rawtypes","unchecked"})
//初始化新NodeNode數(shù)組
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
//舊Node數(shù)組不為null，則進行擴容
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 計算新Map的Node數(shù)組元素下標。如果當前Node節(jié)點沒有后續(xù)節(jié)點，則直接放入新位置
newTab[e.hash & (newCap - 1)] = e;
// 如果當前Node是紅黑樹，則對樹進行處理
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// 處理鏈表
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// (e.hash & oldCap) == 0 元素放在低位區(qū)，否則放在高位區(qū)
// 低位區(qū)：原Node長度的位置；高位區(qū)：原Node長度到擴容后Node長度的位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
//采用尾插法
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 將低位區(qū)的尾結點指向null，并把低位區(qū)的頭結點放入新Node數(shù)組的合適位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 將高位區(qū)的頭結點放到新Node數(shù)組合適的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
##?resize重點代碼發(fā)明
-
?為什么要進行擴容？
????????減少hash碰撞，使HashMap中的結構更簡單。
2. 為什么要以2的倍數(shù)作為擴容的策略？
????????保證HashMap的容量都是2的次冪，便于key的位置計算和擴容的容量計算。
## get方法集解
public V get(Object key) {
Node e;
//獲取key的hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//Node數(shù)組不為null并且其長度大于0并且key位置部位null，則獲取當前key位置的Node，否則返回null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//當前位置的key和入?yún)ey相等，則返回當前Node
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果首Node節(jié)點為空，直接返回null。否則去鏈表或紅黑樹中取值
if ((e = first.next) != null) {
//判斷是否是紅黑樹，是的話在樹中取值
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
????????????????//在鏈表中取值，如果key值相等，則取鏈表中的當前Node節(jié)點
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//返回null
return null;
}
疑問：
現(xiàn)狀：在resize方法中，代碼 hiTail.next = null;?表示將高位區(qū)的尾結點的next指向null。
問："這個操作不能將高位區(qū)和低位區(qū)的Node節(jié)點通過指針相連，那么遍歷鏈表時如何遍歷到低位區(qū)的數(shù)據(jù)？為什么不將高位區(qū)尾節(jié)點的next指向低位區(qū)的頭指針？"
注：
集解 -?引自《本草綱目》，意為收集業(yè)內(nèi)眾家釋義；
發(fā)明 -?引自《本草綱目》，意為筆者獨立的見解，有別于他。
評論
圖片
表情