寫在前
hashMap 在日常項(xiàng)目中用的筆記頻繁，大家都知道hashMap是線程不安全的，在并發(fā)情況下，應(yīng)該用concurrentHashMap,但是，為什么hashMap是線程不安全的，而concurrentHashMap是線程安全的呢？下面我們來具體分析下。
hashMap
大家都知道hashMap的底層是數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，下面是java 1.8中hashMap的數(shù)據(jù)結(jié)構(gòu)示意圖(圖片來源于網(wǎng)絡(luò))：
java 8 在數(shù)據(jù)結(jié)構(gòu)上對(duì)比1.7多了一個(gè)紅黑樹，當(dāng)鏈表的長(zhǎng)度大于8的時(shí)候會(huì)將鏈表轉(zhuǎn)化為紅黑樹，紅黑樹的是一個(gè)自平衡二叉樹，查找算法O(logn)。
在并發(fā)情況下，當(dāng)我們往hashMap中存放的數(shù)據(jù)過多的時(shí)候，尤其在hashMap擴(kuò)容的時(shí)候，在并發(fā)情況下，很容易出問題。
java1.7擴(kuò)容
在hashMap中put元素時(shí)，如果capacity（容量）* loadFactor（裝載因子）大于hashMap中size（鍵值對(duì)的個(gè)數(shù)）時(shí)就會(huì)發(fā)生擴(kuò)容。
/**
* 源碼分析：addEntry(hash, key, value, i)
* 作用：添加鍵值對(duì)（Entry ）到 HashMap中
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 參數(shù)3 = 插入數(shù)組table的索引位置 = 數(shù)組下標(biāo)
// 1. 插入前，先判斷容量是否足夠
// 1.1 若不足夠，則進(jìn)行擴(kuò)容（2倍）、重新計(jì)算Hash值、重新計(jì)算存儲(chǔ)數(shù)組下標(biāo)
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // a. 擴(kuò)容2倍 --> 分析1
hash = (null != key) ? hash(key) : 0; // b. 重新計(jì)算該Key對(duì)應(yīng)的hash值
bucketIndex = indexFor(hash, table.length); // c. 重新計(jì)算該Key對(duì)應(yīng)的hash值的存儲(chǔ)數(shù)組下標(biāo)位置
}
// 1.2 若容量足夠，則創(chuàng)建1個(gè)新的數(shù)組元素（Entry） 并放入到數(shù)組中--> 分析2
createEntry(hash, key, value, bucketIndex);
}
---------------------
/**
* 分析1：resize(2 * table.length)
* 作用：當(dāng)容量不足時(shí)（容量 > 閾值），則擴(kuò)容（擴(kuò)到2倍）
*/
void resize(int newCapacity) {
// 1. 保存舊數(shù)組（old table）
Entry[] oldTable = table;
// 2. 保存舊容量（old capacity ），即數(shù)組長(zhǎng)度
int oldCapacity = oldTable.length;
// 3. 若舊容量已經(jīng)是系統(tǒng)默認(rèn)最大容量了，那么將閾值設(shè)置成整型的最大值，退出
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 4. 根據(jù)新容量（2倍容量）新建1個(gè)數(shù)組，即新table
Entry[] newTable = new Entry[newCapacity];
// 5. 將舊數(shù)組上的數(shù)據(jù)（鍵值對(duì)）轉(zhuǎn)移到新table中，從而完成擴(kuò)容 ->>分析1.1
transfer(newTable);
// 6. 新數(shù)組table引用到HashMap的table屬性上
table = newTable;
// 7. 重新設(shè)置閾值
threshold = (int)(newCapacity * loadFactor);
}
/**
* 分析1.1：transfer(newTable);
* 作用：將舊數(shù)組上的數(shù)據(jù)（鍵值對(duì)）轉(zhuǎn)移到新table中，從而完成擴(kuò)容
* 過程：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入
*/
void transfer(Entry[] newTable) {
// 1. src引用了舊數(shù)組
Entry[] src = table;
// 2. 獲取新數(shù)組的大小 = 獲取新容量大小
int newCapacity = newTable.length;
// 3. 通過遍歷 舊數(shù)組，將舊數(shù)組上的數(shù)據(jù)（鍵值對(duì)）轉(zhuǎn)移到新數(shù)組中
for (int j = 0; j < src.length; j++) {
// 3.1 取得舊數(shù)組的每個(gè)元素
Entry<K,V> e = src[j];
if (e != null) {
// 3.2 釋放舊數(shù)組的對(duì)象引用（for循環(huán)后，舊數(shù)組不再引用任何對(duì)象）
src[j] = null;
do {
// 3.3 遍歷 以該數(shù)組元素為首 的鏈表
// 注：轉(zhuǎn)移鏈表時(shí)，因是單鏈表，故要保存下1個(gè)結(jié)點(diǎn)，否則轉(zhuǎn)移后鏈表會(huì)斷開
Entry<K,V> next = e.next;
// 3.4 重新計(jì)算每個(gè)元素的存儲(chǔ)位置
int i = indexFor(e.hash, newCapacity);
// 3.5 將元素放在數(shù)組上：采用單鏈表的頭插入方式 = 在鏈表頭上存放數(shù)據(jù) = 將數(shù)組位置的原有數(shù)據(jù)放在后1個(gè)指針、將需放入的數(shù)據(jù)放到數(shù)組位置中
// 即 擴(kuò)容后，可能出現(xiàn)逆序：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入
e.next = newTable[i];
newTable[i] = e;
// 3.6 訪問下1個(gè)Entry鏈上的元素，如此不斷循環(huán)，直到遍歷完該鏈表上的所有節(jié)點(diǎn)
e = next;
} while (e != null);
// 如此不斷循環(huán)，直到遍歷完數(shù)組上的所有數(shù)據(jù)元素
}
}
}
在擴(kuò)容resize（）過程中，在將舊數(shù)組上的數(shù)據(jù) 轉(zhuǎn)移到 新數(shù)組上時(shí)，轉(zhuǎn)移操作是：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入，即在轉(zhuǎn)移數(shù)據(jù)、擴(kuò)容后，出現(xiàn)鏈表逆序的情況（下面的過程參考了文章：https://www.cnblogs.com/dongguacai/p/5599100.html）。
正常情況下hashMap擴(kuò)容：
1、假設(shè)我們的hash算法是簡(jiǎn)單的key mod一下表的大?。磾?shù)組的長(zhǎng)度）。
2、最上面是old hash表，其中HASH表的size=2，所以key=3,5,7在mod 2 以后都沖突在table[1]這個(gè)位置上了。
3、接下來HASH表擴(kuò)容，resize=4，然后所有的<key,value>重新進(jìn)行散列分布，過程如下：
單線程情況下，沒有任何問題。
并發(fā)情況下hashMap擴(kuò)容：
假設(shè)我們有兩個(gè)線程，分別用紅色和藍(lán)色標(biāo)注了。
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 {
Entry<K,V> next = e.next;//①
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
假設(shè)線程1在執(zhí)行完①處阻塞，線程2，開始執(zhí)行，線程2執(zhí)行上面的代碼，這個(gè)時(shí)候的狀態(tài)是：
（這里要特別清楚一點(diǎn)，線程1和線程2的Entry<K,V> e 指向的是同一個(gè)數(shù)組對(duì)象，有一個(gè)改變了，另一個(gè)指向的內(nèi)容也就變了，另外，newTable數(shù)組是線程私有的。）
接下來，線程1被喚醒，繼續(xù)執(zhí)行，此時(shí)，e指向的是key=3的節(jié)點(diǎn)，指向完后線程1的newTable[]中的數(shù)據(jù)為：
接著，e指向key=7的節(jié)點(diǎn)，e!=null繼續(xù)執(zhí)行
next=e.next=3（線程2執(zhí)行完之后結(jié)構(gòu)發(fā)生了變化節(jié)點(diǎn)7指向了節(jié)點(diǎn)3）
e.next = newTable[i];節(jié)點(diǎn)7指向節(jié)點(diǎn)3（這時(shí)要看線程1的newTable）
newTable[i] = e;newTable[i]指向節(jié)點(diǎn)7
e = next；e節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)3
Entry<K,V> next = e.next e節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為null；
e.next = newTable[i];3節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向節(jié)點(diǎn)7
newTable[i] = e;newTable[i]指向節(jié)點(diǎn)3；
e=next；e為空 結(jié)束循環(huán)；
這次擴(kuò)容結(jié)束了。但是后續(xù)如果有查詢（無論是查詢的迭代還是擴(kuò)容），都會(huì)hang死在table【3】這個(gè)位置上。同時(shí)，這個(gè)過程中發(fā)現(xiàn)節(jié)點(diǎn)5在線程1丟掉了，所以多線程下put，也可能造成元素丟失。
Java1.8擴(kuò)容
首先，看下hashMap中怎么計(jì)算key的hash值：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
圖中的 hash 是由鍵的 hashCode 產(chǎn)生。計(jì)算余數(shù)時(shí)，由于 n 比較小，hash 只有低4位參與了計(jì)算，高位的計(jì)算可以認(rèn)為是無效的。這樣導(dǎo)致了計(jì)算結(jié)果只與低位信息有關(guān)，高位數(shù)據(jù)沒發(fā)揮作用。為了處理這個(gè)缺陷，我們可以上圖中的 hash 高4位數(shù)據(jù)與低4位數(shù)據(jù)進(jìn)行異或運(yùn)算，即 hash ^ (hash >>> 4)。通過這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進(jìn)行異或，以此加大低位信息的隨機(jī)性，變相的讓高位數(shù)據(jù)參與到計(jì)算中。此時(shí)的計(jì)算過程如下：
在 Java 中，hashCode 方法產(chǎn)生的 hash 是 int 類型，32 位寬。前16位為高位，后16位為低位，所以要右移16位。
下面重點(diǎn)講下hashMap的插入操作：
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;
// 初始化桶數(shù)組 table，table 被延遲到插入新數(shù)據(jù)時(shí)再進(jìn)行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果桶中不包含鍵值對(duì)節(jié)點(diǎn)引用，則將新鍵值對(duì)節(jié)點(diǎn)的引用存入桶中即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果鍵的值以及節(jié)點(diǎn) hash 等于鏈表中的第一個(gè)鍵值對(duì)節(jié)點(diǎn)時(shí)，則將 e 指向該鍵值對(duì)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中的引用類型為 TreeNode，則調(diào)用紅黑樹的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 對(duì)鏈表進(jìn)行遍歷，并統(tǒng)計(jì)鏈表長(zhǎng)度
for (int binCount = 0; ; ++binCount) {
// 鏈表中不包含要插入的鍵值對(duì)節(jié)點(diǎn)時(shí)，則將該節(jié)點(diǎn)接在鏈表的最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果鏈表長(zhǎng)度大于或等于樹化閾值，則進(jìn)行樹化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 條件為 true，表示當(dāng)前鏈表包含要插入的鍵值對(duì)，終止遍歷
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判斷要插入的鍵值對(duì)是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對(duì)的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 鍵值對(duì)數(shù)量超過閾值時(shí)，則進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
插入邏輯并不復(fù)雜，下面看下擴(kuò)容機(jī)制(一下內(nèi)容參考https://segmentfault.com/a/1190000012926722)：
在 HashMap 中，桶數(shù)組的長(zhǎng)度均是2的冪，閾值大小為桶數(shù)組長(zhǎng)度與負(fù)載因子的乘積。當(dāng) HashMap 中的鍵值對(duì)數(shù)量超過閾值時(shí)，進(jìn)行擴(kuò)容。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果 table 不為空，表明已經(jīng)初始化過了
if (oldCap > 0) {
// 當(dāng) table 容量超過容量最大值，則不再擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按舊容量和閾值的2倍計(jì)算新容量和閾值的大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
/*
* 初始化時(shí)，將 threshold 的值賦值給 newCap，
* HashMap 使用 threshold 變量暫時(shí)保存 initialCapacity 參數(shù)的值
*/
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/*
* 調(diào)用無參構(gòu)造方法時(shí)，桶數(shù)組容量為默認(rèn)容量，
* 閾值為默認(rèn)容量與默認(rèn)負(fù)載因子乘積
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 為 0 時(shí)，按閾值計(jì)算公式進(jìn)行計(jì)算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 創(chuàng)建新的桶數(shù)組，桶數(shù)組的初始化也是在這里完成的
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果舊的桶數(shù)組不為空，則遍歷桶數(shù)組，并將鍵值對(duì)映射到新的桶數(shù)組中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 重新映射時(shí)，需要對(duì)紅黑樹進(jìn)行拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷鏈表，并將鏈表節(jié)點(diǎn)按原順序進(jìn)行分組
do {
next = e.next;
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);
// 將分組后的鏈表映射到新桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
往底層數(shù)據(jù)結(jié)構(gòu)中插入節(jié)點(diǎn)時(shí)，一般都是先通過模運(yùn)算計(jì)算桶位置，接著把節(jié)點(diǎn)放入桶中即可,在 JDK 1.8 中，則對(duì)這個(gè)過程進(jìn)行了一定的優(yōu)化
上圖中，桶數(shù)組大小 n = 16，hash1 與 hash2 不相等。但因?yàn)橹挥泻?位參與求余，所以結(jié)果相等。當(dāng)桶數(shù)組擴(kuò)容后，n 由16變成了32，對(duì)上面的 hash 值重新進(jìn)行映射：
擴(kuò)容后，參與模運(yùn)算的位數(shù)由4位變?yōu)榱?位。由于兩個(gè) hash 第5位的值是不一樣，所以兩個(gè) hash 算出的結(jié)果也不一樣。上面的計(jì)算過程并不難理解，繼續(xù)往下分析。
假設(shè)我們上圖的桶數(shù)組進(jìn)行擴(kuò)容，擴(kuò)容后容量 n = 16，重新映射過程如下:
依次遍歷鏈表，并計(jì)算節(jié)點(diǎn) hash & oldCap 的值。如下圖所示
如果值為0，將 loHead 和 loTail 指向這個(gè)節(jié)點(diǎn)。如果后面還有節(jié)點(diǎn) hash & oldCap 為0的話，則將節(jié)點(diǎn)鏈入 loHead 指向的鏈表中，并將 loTail 指向該節(jié)點(diǎn)。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節(jié)點(diǎn)。完成遍歷后，可能會(huì)得到兩條鏈表，此時(shí)就完成了鏈表分組：
最后再將這兩條鏈接存放到相應(yīng)的桶中，完成擴(kuò)容。如下圖：
從上圖可以發(fā)現(xiàn)，重新映射后，兩條鏈表中的節(jié)點(diǎn)順序并未發(fā)生變化，還是保持了擴(kuò)容前的順序。以上就是 JDK 1.8 中 HashMap 擴(kuò)容的代碼講解。另外再補(bǔ)充一下，JDK 1.8 版本下 HashMap 擴(kuò)容效率要高于之前版本。如果大家看過 JDK 1.7 的源碼會(huì)發(fā)現(xiàn)，JDK 1.7 為了防止因 hash 碰撞引發(fā)的拒絕服務(wù)攻擊，在計(jì)算 hash 過程中引入隨機(jī)種子。以增強(qiáng) hash 的隨機(jī)性，使得鍵值對(duì)均勻分布在桶數(shù)組中。在擴(kuò)容過程中，相關(guān)方法會(huì)根據(jù)容量判斷是否需要生成新的隨機(jī)種子，并重新計(jì)算所有節(jié)點(diǎn)的 hash。而在 JDK 1.8 中，則通過引入紅黑樹替代了該種方式。從而避免了多次計(jì)算 hash 的操作，提高了擴(kuò)容效率。
雖然jdk1.8中hashMap擴(kuò)容避免了死循環(huán)，但是，在并發(fā)情況下還是有可能取到空值的。
