上一篇文章中提到了ThreadLocalMap是使用開放地址法來解決沖突問題的，而我們今天的主角HashMap是采用了鏈表法來處理沖突的,什么是鏈表法呢?
在散列表中，每個(gè) “ 桶(bucket)” 或者 “ 槽(slot)” 會(huì)對(duì)應(yīng)一條鏈表，所有散列值相同的元素我們都放到相同槽位對(duì)應(yīng)的鏈表中。
jdk8和jdk7不一樣，jdk7中沒有紅黑樹,數(shù)組中只掛載鏈表。而jdk8中在桶容量大于等于64且鏈表節(jié)點(diǎn)數(shù)大于等于8的時(shí)候轉(zhuǎn)換為紅黑樹。當(dāng)紅黑樹節(jié)點(diǎn)數(shù)量小于6時(shí)又會(huì)轉(zhuǎn)換為鏈表。
插入
但插入的時(shí)候,我們只需要通過散列函數(shù)計(jì)算出對(duì)應(yīng)的槽位,將其插入到對(duì)應(yīng)鏈表或者紅黑樹即可。如果此時(shí)元素?cái)?shù)量超過了一定值則會(huì)進(jìn)行擴(kuò)容，同時(shí)進(jìn)行rehash.
查找或者刪除
通過散列函數(shù)計(jì)算出對(duì)應(yīng)的槽，然后遍歷鏈表或者刪除
鏈表為什么會(huì)轉(zhuǎn)為紅黑樹?
上一篇文章有提到過通過裝載因子來判定空閑槽位還有多少，如果超過裝載因子的值就會(huì)動(dòng)態(tài)擴(kuò)容,HashMap會(huì)擴(kuò)容為原來的兩倍大小(初始容量為16,即槽(數(shù)組)的大小為16)。但是無論負(fù)載因子和散列函數(shù)設(shè)得再合理，也避免不了鏈表過長(zhǎng)的情況，一旦鏈表過長(zhǎng)查找和刪除元素就比較耗時(shí)，影響HashMap性能,所以JDK8中對(duì)其進(jìn)行了優(yōu)化，當(dāng)鏈表長(zhǎng)度大于等于8的時(shí)候?qū)㈡湵磙D(zhuǎn)換為紅黑樹，利用紅黑樹的特點(diǎn)(查找、插入、刪除的時(shí)間復(fù)雜度最壞為O(logn))，可以提高HashMap的性能。當(dāng)節(jié)點(diǎn)個(gè)數(shù)少于6個(gè)的時(shí)候，又會(huì)將紅黑樹轉(zhuǎn)化為鏈表。因?yàn)樵跀?shù)據(jù)量較小的情況下，紅黑樹要維持平衡，比起鏈表來，性能上的優(yōu)勢(shì)并不明顯，而且編碼難度比鏈表要大上不少。
源碼分析
構(gòu)造方法以及重要屬性
public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity);
public HashMap();
HashMap的構(gòu)造方法中可以分別指定初始化容量(bucket大小)以及負(fù)載因子，如果不指定默認(rèn)值分別是16和0.75.它幾個(gè)重要屬性如下：
// 初始化容量，必須要2的n次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 負(fù)載因子默認(rèn)值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 需要從鏈表轉(zhuǎn)換為紅黑樹時(shí),鏈表節(jié)點(diǎn)的最小長(zhǎng)度
static final int TREEIFY_THRESHOLD = 8;
// 轉(zhuǎn)換為紅黑樹時(shí)數(shù)組的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// resize操作時(shí),紅黑樹節(jié)點(diǎn)個(gè)數(shù)小于6則轉(zhuǎn)換為鏈表。
static final int UNTREEIFY_THRESHOLD = 6;
// HashMap閾值，用于判斷是否需要擴(kuò)容(threshold = 容量*loadFactor)
int threshold;
// 負(fù)載因子
final float loadFactor;
// 鏈表節(jié)點(diǎn)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
// 保存數(shù)據(jù)的數(shù)組
transient Node<K,V>[] table;
// 紅黑樹節(jié)點(diǎn)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
上面的table就是存儲(chǔ)數(shù)據(jù)的數(shù)組(可以叫做桶或者槽),數(shù)組掛載的是鏈表或者紅黑樹。值得一提的是構(gòu)造HashMap的時(shí)候并沒有初始化數(shù)組容量，而是在第一次put元素的時(shí)候才進(jìn)行初始化的。
hash函數(shù)的設(shè)計(jì)
int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
int index = hash & (tab.length-1);
從上面可以看出,key為null是時(shí)候放到數(shù)組中的第一個(gè)位置的,我們一般定位key應(yīng)當(dāng)存放在數(shù)組哪個(gè)位置的時(shí)候一般是這樣做的 key.hashCode() % tab.length。但是當(dāng)tab.length是2的n次冪的時(shí)候，就可以轉(zhuǎn)換為 A % B = A & (B-1);所以 index = hash & (tab.length-1)就可以理解了。
這里是使用了除留余數(shù)法的理念來設(shè)計(jì)的,可以可能減少hash沖突
除留余數(shù)法 : 用關(guān)鍵字K除以某個(gè)不大于hash表長(zhǎng)度m的數(shù)p,將所得余數(shù)作為hash表地址
比如x/8=x>>3,即把x右移3位，得到了x/8的商，被移掉的部分(后三位)，則是x%8，也就是余數(shù)。
而對(duì)于hash值的運(yùn)算為什么是(h = key.hashCode()) ^ (h >>> 16)呢？也就是為什么要向右移16位呢?直接使用 key.hashCode() & (tab.length -1)不好嗎？
如果這樣做，由于tab.length肯定是遠(yuǎn)遠(yuǎn)小于hash值的,所以位運(yùn)算的時(shí)候只有低位才參與運(yùn)算，而高位毫無作為，會(huì)帶來hash沖突的風(fēng)險(xiǎn)。
而hashcode本身是一個(gè)32位整形值，向右移位16位之后再進(jìn)行異或運(yùn)行計(jì)算出來的整形將具有高位和低位的性質(zhì)，就可以得到一個(gè)非常隨機(jī)的hash值，在通過除留余數(shù)法，得到的index就更低概率的減少了沖突。
插入數(shù)據(jù)
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. 如果數(shù)組未初始化,則初始化數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 如果當(dāng)前節(jié)點(diǎn)未被插入數(shù)據(jù)(未碰撞),則直接new一個(gè)節(jié)點(diǎn)進(jìn)行插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 3. 碰撞了,已存在相同的key,則進(jìn)行覆蓋
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 4. 碰撞后發(fā)現(xiàn)為樹結(jié)構(gòu)，則掛載在樹上
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 5. 進(jìn)行尾插入,如果鏈表節(jié)點(diǎn)數(shù)達(dá)到上線則轉(zhuǎn)換為紅黑樹
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 6. 鏈表中碰撞了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 7. 用新value替換舊的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 8. 操作閾值則進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
// 給LinkedHashMap實(shí)現(xiàn)
afterNodeInsertion(evict);
return null;
}
簡(jiǎn)述下put的邏輯，它主要分為以下幾個(gè)步驟:
- 首先判斷是否初始化，如果未初始化則初始化數(shù)組,初始容量為16
- 通過hash&(n-1)獲取數(shù)組下標(biāo)，如果該位置為空，表示未碰撞，直接插入數(shù)據(jù)
- 發(fā)生碰撞且存在相同的key，則在后面處理中直接進(jìn)行覆蓋
- 碰撞后發(fā)現(xiàn)為樹結(jié)構(gòu)，則直接掛載到紅黑樹上
- 碰撞后發(fā)現(xiàn)為鏈表結(jié)構(gòu)，則進(jìn)行尾插入，當(dāng)鏈表容量大于等于8的時(shí)候轉(zhuǎn)換為樹節(jié)點(diǎn)
- 發(fā)現(xiàn)在鏈表中進(jìn)行碰撞了，則在后面處理直接覆蓋
- 發(fā)現(xiàn)之前存在相同的key,只直接用新值替換舊值
- map的容量(存儲(chǔ)元素的數(shù)量)大于閾值則進(jìn)行擴(kuò)容，擴(kuò)容為之前容量的2倍
擴(kuò)容
resize()方法中，如果發(fā)現(xiàn)當(dāng)前數(shù)組未初始化，則會(huì)初始化數(shù)組。如果已經(jīng)初始化，則會(huì)將數(shù)組容量擴(kuò)容為之前的兩倍，同時(shí)進(jìn)行rehash(將舊數(shù)組的數(shù)據(jù)移動(dòng)到新的數(shù)組).JDK8的rehash過程很有趣，相比JDK7做了不少優(yōu)化，我們來看下這里的rehash過程。
// 數(shù)組擴(kuò)容為之前2倍大小的代碼省略，這里主要分析rehash過程。
if (oldTab != null) {
// 遍歷舊數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1. 如果舊數(shù)組中不存在碰撞,則直接移動(dòng)到新數(shù)組的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 2. 如果存在碰撞，且節(jié)點(diǎn)類型是樹節(jié)點(diǎn)，則進(jìn)行樹節(jié)點(diǎn)拆分(掛載到擴(kuò)容后的數(shù)組中或者轉(zhuǎn)為鏈表)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 3. 處理沖突是鏈表的情況,會(huì)保留原有節(jié)點(diǎn)的順序
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 4. 判斷擴(kuò)容后元素是否在原有的位置(這里非常巧妙,下面會(huì)分析)
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 5. 元素不是在原有位置
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 6. 將擴(kuò)容后未改變index的元素復(fù)制到新數(shù)組
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 7. 將擴(kuò)容后改變了index位置的元素復(fù)制到新數(shù)組
if (hiTail != null) {
hiTail.next = null;
// 8. index改變后,新的下標(biāo)是j+oldCap,這里也很巧妙，下面會(huì)分析
newTab[j + oldCap] = hiHead;
}
}
}
}
}
上面的代碼中展現(xiàn)了整個(gè)rehash的過程，先遍歷舊數(shù)組中的元素，接著做下面的事情
- 如果舊數(shù)組中不存在數(shù)據(jù)碰撞(未掛載鏈表或者紅黑樹),那么直接將元素賦值到新數(shù)組中，其中
index=e.hash & (newCap - 1)。 - 如果存在碰撞，且節(jié)點(diǎn)類型是樹節(jié)點(diǎn)，則進(jìn)行樹節(jié)點(diǎn)拆分(掛載到擴(kuò)容后的數(shù)組中或者轉(zhuǎn)為鏈表)
- 如果存在碰撞，且節(jié)點(diǎn)是鏈表，則處理鏈表的情況,rehash過程會(huì)保留節(jié)點(diǎn)原始順序(JDK7中不會(huì)保留，這也是導(dǎo)致jdk7中多線程出現(xiàn)死循環(huán)的原因)
- 判斷元素在擴(kuò)容后是否還處于原有的位置，這里通過
(e.hash & oldCap) == 0判斷,oldCap表示擴(kuò)容前數(shù)組的大小。 - 發(fā)現(xiàn)元素不是在原有位置，更新hiTail和hiHead的指向關(guān)系
- 將擴(kuò)容后未改變index的元素復(fù)制到新數(shù)組
- 將擴(kuò)容后改變了index位置的元素復(fù)制到新數(shù)組，新數(shù)組的下標(biāo)是
j + oldCap。
其中第4點(diǎn)和第5點(diǎn)中將鏈表的元素分為兩部分(do..while部分)，一部分是rehash后index未改變的元素，一部分是index被改變的元素。分別用兩個(gè)指針來指向頭尾節(jié)點(diǎn)。
比如當(dāng)oldCap=8時(shí),1-->9-->17都掛載在tab[1]上,而擴(kuò)容后，1-->17掛載在tab[1]上,9掛載在tab[9]上。
那么是如何確定rehash后index是否被改變呢？改變之后的index又變成了多少呢？
這里的設(shè)計(jì)很是巧妙，還記得HashMap中數(shù)組大小是2的n次冪嗎?當(dāng)我們計(jì)算索引位置的時(shí)候，使用的是 e.hash & (tab.length -1)。
這里我們討論數(shù)組大小從8擴(kuò)容到16的過程。
tab.length -1 = 7 0 0 1 1 1
e.hashCode = x 0 x x x x
==============================
0 0 y y y
可以發(fā)現(xiàn)在擴(kuò)容前index的位置由hashCode的低三位來決定。那么擴(kuò)容后呢？
tab.length -1 = 15 0 1 1 1 1
e.hashCode = x x x x x x
==============================
0 z y y y
擴(kuò)容后，index的位置由低四位來決定,而低三位和擴(kuò)容前一致。也就是說擴(kuò)容后index的位置是否改變是由高字節(jié)來決定的,也就是說我們只需要將hashCode和高位進(jìn)行運(yùn)算即可得到index是否改變。
而剛好擴(kuò)容之后的高位和oldCap的高位一樣。如上面的15二進(jìn)制是1111,而8的二進(jìn)制是1000,他們的高位都是一樣的。所以我們通過e.hash & oldCap運(yùn)算的結(jié)果即可判斷index是否改變。
同理，如果擴(kuò)容后index該變了。新的index和舊的index的值也是高位不同，其新值剛好是 oldIndex + oldCap的值。所以當(dāng)index改變后,新的index是 j + oldCap。
至此,resize方法結(jié)束,元素被插入到了該有的位置。
get()
get()的方法就相對(duì)來說要簡(jiǎn)單一些了，它最重要的就是找到key是存放在哪個(gè)位置
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 首先(n-1) & hash確定元素位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2. 判斷第一個(gè)元素是否是我們需要找的元素
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 3. 節(jié)點(diǎn)如果是樹節(jié)點(diǎn),則在紅黑樹中尋找元素
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
4. 在鏈表中尋找對(duì)應(yīng)的節(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;
}
remove
remove方法尋找節(jié)點(diǎn)的過程和get()方法尋找節(jié)點(diǎn)的過程是一樣的，這里我們主要分析尋找到節(jié)點(diǎn)后是如何處理的
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 1. 刪除樹節(jié)點(diǎn),刪除時(shí)如果不平衡會(huì)重新移動(dòng)節(jié)點(diǎn)位置
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 刪除的節(jié)點(diǎn)是鏈表第一個(gè)節(jié)點(diǎn),則直接將第二個(gè)節(jié)點(diǎn)賦值為第一個(gè)節(jié)點(diǎn)
else if (node == p)
tab[index] = node.next;
// 刪除的節(jié)點(diǎn)是鏈表的中間節(jié)點(diǎn)，這里的p為node的prev節(jié)點(diǎn)
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
remove方法中，最為復(fù)雜的部分應(yīng)該是removeTreeNode部分，因?yàn)閯h除紅黑樹節(jié)點(diǎn)后，可能需要退化為鏈表節(jié)點(diǎn)，還可能由于不滿足紅黑樹特點(diǎn)，需要移動(dòng)節(jié)點(diǎn)位置。
代碼也比較多，這里就不貼上來了。但也因此佐證了為什么不全部使用紅黑樹來代替鏈表。
JDK7擴(kuò)容時(shí)導(dǎo)致的死循環(huán)問題
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
// B線程執(zhí)行到這里之后就暫停了
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
// 會(huì)把元素放到鏈表頭，所以擴(kuò)容后數(shù)據(jù)會(huì)被倒置
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
擴(kuò)容時(shí)上面的代碼容易導(dǎo)致死循環(huán),是怎樣導(dǎo)致的呢？假設(shè)有兩個(gè)線程A和B都在執(zhí)行這一段代碼，數(shù)組大小由2擴(kuò)容到4,在擴(kuò)容前tab[1]=1-->5-->9。
當(dāng)B線程執(zhí)行到 next = e.next時(shí)讓出時(shí)間片,A線程執(zhí)行完整段代碼但是還沒有將內(nèi)部的table設(shè)置為新的newTable時(shí)，線程B繼續(xù)執(zhí)行。
此時(shí)A線程執(zhí)行完成之后，掛載在tab[1]的元素是9-->5-->1,注意這里的順序被顛倒了。此時(shí)e = 1, next = 5;
tab[i]的按照循環(huán)次數(shù)變更順序, 1. tab[i]=1, 2. tab[i]=5-->1, 3. tab[i]=9-->5-->1
同樣B線程我們也按照循環(huán)次數(shù)來分析
- 第一次循環(huán)執(zhí)行完成后,newTable[i]=1, e = 5
- 第二次循環(huán)完成后: newTable[i]=5-->1, e = 1。
- 第三次循環(huán),e沒有next,所以next指向null。當(dāng)執(zhí)行e.next = newTable[i](1-->5)的時(shí)候,就形成了 1-->5-->1的環(huán),再執(zhí)行newTable[i]=e,此時(shí)newTable[i] = 1-->5-->1。
當(dāng)在數(shù)組該位置get尋找對(duì)應(yīng)的key的時(shí)候，就發(fā)生了死循環(huán),引起CPU 100%問題。
而JDK8就不會(huì)出現(xiàn)這個(gè)問題,它在這里就有一個(gè)優(yōu)化，它使用了兩個(gè)指針來分別指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，而且還保證了元素原本的順序。
當(dāng)然HashMap仍然是不安全的,所以在多線程并發(fā)條件下推薦使用ConcurrentHashMap。
你的點(diǎn)贊是對(duì)我最大的支持，當(dāng)然你關(guān)注我就更好了
