源碼詳解
1. 構(gòu)造函數(shù)
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity,float loadFactor)
HashMap(Map<? extends K, ? extends V> m)
2. 常量
DEFAULT_INITIAL_CAPACITY = 1 << 4 // 初始化容量 16
MAXIMUM_CAPACITY = 1 << 30 // 最大容量 1 073 741 824
DEFAULT_LOAD_FACTOR = 0.75f // 負(fù)載因子， 超過 ‘容量*負(fù)載因子’，開始擴(kuò)容 *2
TREEIFY_THRESHOLD = 8 // 一個桶樹化的閥值困檩，當(dāng)key.hashcode,相同超過8四瘫，會轉(zhuǎn)成紅黑樹
UNTREEIFY_THRESHOLD = 6 //一個桶鏈表化的閥值捶索，當(dāng)key.hashcode,相同低于6八孝，會轉(zhuǎn)成鏈表
MIN_TREEIFY_CAPACITY = 64 //哈希表最小樹形化容量董朝，<64,即使key.hashcode超過8也不會樹化
3. 核心函數(shù)
put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1、初始化hash表唆阿，由此可見 hashMap的初始化是在調(diào)用時益涧，不是在調(diào)用構(gòu)造函數(shù)時
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2锈锤、計算key存放下標(biāo)：當(dāng)前數(shù)組大小-1 & 當(dāng)前hash值驯鳖。如果此下標(biāo)下沒有元素，直接放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//3久免、如果節(jié)點(diǎn)存在直接替換舊值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4浅辙、紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//5、鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長度大于8轉(zhuǎn)為紅黑樹處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key 存在直接覆蓋舊值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//allbacks to allow LinkedHashMap post-actions
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//6阎姥、超過容量记舆，就擴(kuò)容
if (++size > threshold)
resize();
//allbacks to allow LinkedHashMap post-actions 為linkedHashMap服務(wù)的，輸入和輸出有序
afterNodeInsertion(evict);
return null;
}
get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//先判斷頭節(jié)點(diǎn)呼巴，算法和插入時一致 (n-1)&hash
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果頭節(jié)點(diǎn)是樹節(jié)點(diǎn)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//遞歸查找與key相同桶的節(jié)點(diǎn)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
4. 總結(jié)
1泽腮、initialCapacity默認(rèn)16，元素達(dá)到容量的0.75倍時擴(kuò)容衣赶；擴(kuò)容在原來的容量*2
2诊赊、當(dāng)key.hashcode相同時，會在當(dāng)前節(jié)點(diǎn)上維護(hù)一個鏈表結(jié)構(gòu)府瞄，當(dāng)鏈表個數(shù)大于8且當(dāng)前hash表中容量不小于64碧磅，會將鏈表轉(zhuǎn)換成紅黑樹結(jié)構(gòu)；相反如果樹的個數(shù)低于6，會在轉(zhuǎn)回鏈表
3鲸郊、hashmap的初始化在調(diào)用put的時候執(zhí)行
4丰榴、initialCapacity值為2的冪次方
5、hashmap在并發(fā)中會造成死循環(huán)秆撮，節(jié)點(diǎn)回環(huán)
5. 源碼解惑
- 默認(rèn)值為什么是16四濒，負(fù)載因子為什么是0.75？
看下源碼像吻，注釋上說 ：Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity峻黍。
在理想情況下,使用隨機(jī)哈希碼,節(jié)點(diǎn)出現(xiàn)的頻率在hash桶中遵循泊松分布，同時給出了桶中元素個數(shù)和概率的對照表拨匆。
從上面的表中可以看到當(dāng)桶中元素到達(dá)8個的時候姆涩，概率已經(jīng)變得非常小，也就是說用0.75作為加載因子惭每，每個碰撞位置的鏈表長度超過８個是幾乎不可能的骨饿。
為什么是16，不是15或者18 參考問題2台腥。
- 為什么容量要是2的冪次方宏赘？
The default initial capacity - MUST be a power of two.
原因是減少hash碰撞的概率。計算元素下標(biāo)的方式：(n - 1) & hash.
舉個栗子：如果一個容量是15黎侈，兩個元素hash值分別是8察署、9。根據(jù)(n-1)&hash 計算 (15-1)&8 = 1110&1000 =1000; (15-1)&9=1110&1001=1000峻汉。14的最后一位是0贴汪，&上0、1都是0休吠，所以1的位置永遠(yuǎn)不能存儲數(shù)據(jù)扳埂。所以0001、0011瘤礁、0101阳懂、0111這些都是無法存儲數(shù)據(jù)的，增加了hash碰撞的幾率.
-
hashmap在多線程下為什么會死循環(huán)柜思？
原因是hashmap是線程不安全的岩调，在put的時候會造成節(jié)點(diǎn)回環(huán)。
節(jié)點(diǎn)回環(huán)形成的原因：
hashMap擴(kuò)容的時候赡盘，會重新計算下標(biāo)号枕，放入新Node中，摘取resize()關(guān)鍵代碼亡脑，在多線程下堕澄，T1在44行的時候被掛起邀跃，由T2執(zhí)行擴(kuò)容操作，例如蛙紫，在容量為2的hashMap中拍屑，存放3、7坑傅、僵驰，T2執(zhí)行
image.png
擴(kuò)容后
這時候由T1執(zhí)行，T1執(zhí)行的時候 e = oldTab[j] 指向了key:7 ,e.next = key:3唁毒，將key:7放入newTable,然后e和e.next向下移 會發(fā)現(xiàn)key:3的next =key:7 蒜茴，這時候環(huán)型連接形成了
