寫在前
hashMap 在日常項目中用的筆記頻繁猎提，大家都知道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)上對比1.7多了一個紅黑樹页藻，當鏈表的長度大于8的時候會將鏈表轉(zhuǎn)化為紅黑樹桨嫁，紅黑樹的是一個自平衡二叉樹，查找算法O(logn)份帐。
在并發(fā)情況下璃吧，當我們往hashMap中存放的數(shù)據(jù)過多的時候，尤其在hashMap擴容的時候废境，在并發(fā)情況下畜挨，很容易出問題筒繁。
java1.7擴容
在hashMap中put元素時，如果capacity（容量）* loadFactor（裝載因子）大于hashMap中size（鍵值對的個數(shù)）時就會發(fā)生擴容巴元。
/**
* 源碼分析：addEntry(hash, key, value, i)
* 作用：添加鍵值對（Entry ）到 HashMap中
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 參數(shù)3 = 插入數(shù)組table的索引位置 = 數(shù)組下標
// 1. 插入前毡咏，先判斷容量是否足夠
// 1.1 若不足夠，則進行擴容（2倍）务冕、重新計算Hash值血当、重新計算存儲數(shù)組下標
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // a. 擴容2倍 --> 分析1
hash = (null != key) ? hash(key) : 0; // b. 重新計算該Key對應(yīng)的hash值
bucketIndex = indexFor(hash, table.length); // c. 重新計算該Key對應(yīng)的hash值的存儲數(shù)組下標位置
}
// 1.2 若容量足夠，則創(chuàng)建1個新的數(shù)組元素（Entry） 并放入到數(shù)組中--> 分析2
createEntry(hash, key, value, bucketIndex);
}
---------------------
/**
* 分析1：resize(2 * table.length)
* 作用：當容量不足時（容量 > 閾值）禀忆，則擴容（擴到2倍）
*/
void resize(int newCapacity) {
// 1. 保存舊數(shù)組（old table）
Entry[] oldTable = table;
// 2. 保存舊容量（old capacity ）臊旭，即數(shù)組長度
int oldCapacity = oldTable.length;
// 3. 若舊容量已經(jīng)是系統(tǒng)默認最大容量了，那么將閾值設(shè)置成整型的最大值箩退，退出
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 4. 根據(jù)新容量（2倍容量）新建1個數(shù)組离熏，即新table
Entry[] newTable = new Entry[newCapacity];
// 5. 將舊數(shù)組上的數(shù)據(jù)（鍵值對）轉(zhuǎn)移到新table中，從而完成擴容 ->>分析1.1
transfer(newTable);
// 6. 新數(shù)組table引用到HashMap的table屬性上
table = newTable;
// 7. 重新設(shè)置閾值
threshold = (int)(newCapacity * loadFactor);
}
/**
* 分析1.1：transfer(newTable);
* 作用：將舊數(shù)組上的數(shù)據(jù)（鍵值對）轉(zhuǎn)移到新table中戴涝，從而完成擴容
* 過程：按舊鏈表的正序遍歷鏈表滋戳、在新鏈表的頭部依次插入
*/
void transfer(Entry[] newTable) {
// 1. src引用了舊數(shù)組
Entry[] src = table;
// 2. 獲取新數(shù)組的大小 = 獲取新容量大小
int newCapacity = newTable.length;
// 3. 通過遍歷 舊數(shù)組，將舊數(shù)組上的數(shù)據(jù)（鍵值對）轉(zhuǎn)移到新數(shù)組中
for (int j = 0; j < src.length; j++) {
// 3.1 取得舊數(shù)組的每個元素
Entry<K,V> e = src[j];
if (e != null) {
// 3.2 釋放舊數(shù)組的對象引用（for循環(huán)后啥刻，舊數(shù)組不再引用任何對象）
src[j] = null;
do {
// 3.3 遍歷 以該數(shù)組元素為首 的鏈表
// 注：轉(zhuǎn)移鏈表時奸鸯，因是單鏈表，故要保存下1個結(jié)點可帽，否則轉(zhuǎn)移后鏈表會斷開
Entry<K,V> next = e.next;
// 3.4 重新計算每個元素的存儲位置
int i = indexFor(e.hash, newCapacity);
// 3.5 將元素放在數(shù)組上：采用單鏈表的頭插入方式 = 在鏈表頭上存放數(shù)據(jù) = 將數(shù)組位置的原有數(shù)據(jù)放在后1個指針娄涩、將需放入的數(shù)據(jù)放到數(shù)組位置中
// 即 擴容后，可能出現(xiàn)逆序：按舊鏈表的正序遍歷鏈表映跟、在新鏈表的頭部依次插入
e.next = newTable[i];
newTable[i] = e;
// 3.6 訪問下1個Entry鏈上的元素蓄拣，如此不斷循環(huán)，直到遍歷完該鏈表上的所有節(jié)點
e = next;
} while (e != null);
// 如此不斷循環(huán)努隙，直到遍歷完數(shù)組上的所有數(shù)據(jù)元素
}
}
}
在擴容resize（）過程中球恤，在將舊數(shù)組上的數(shù)據(jù) 轉(zhuǎn)移到 新數(shù)組上時，轉(zhuǎn)移操作是：按舊鏈表的正序遍歷鏈表荸镊、在新鏈表的頭部依次插入咽斧，即在轉(zhuǎn)移數(shù)據(jù)、擴容后躬存，出現(xiàn)鏈表逆序的情況（下面的過程參考了文章：https://www.cnblogs.com/dongguacai/p/5599100.html）收厨。
正常情況下hashMap擴容：
1、假設(shè)我們的hash算法是簡單的key mod一下表的大杏殴埂（即數(shù)組的長度）诵叁。
2、最上面是old hash表钦椭，其中HASH表的size=2拧额，所以key=3,5,7在mod 2 以后都沖突在table[1]這個位置上了碑诉。
3、接下來HASH表擴容侥锦，resize=4进栽，然后所有的<key,value>重新進行散列分布，過程如下：
單線程情況下恭垦，沒有任何問題快毛。
并發(fā)情況下hashMap擴容：
假設(shè)我們有兩個線程，分別用紅色和藍色標注了番挺。
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í)行上面的代碼襟衰，這個時候的狀態(tài)是：
（這里要特別清楚一點，線程1和線程2的Entry<K,V> e 指向的是同一個數(shù)組對象粪摘，有一個改變了瀑晒，另一個指向的內(nèi)容也就變了，另外徘意，newTable數(shù)組是線程私有的苔悦。）
接下來，線程1被喚醒椎咧，繼續(xù)執(zhí)行玖详，此時，e指向的是key=3的節(jié)點邑退，指向完后線程1的newTable[]中的數(shù)據(jù)為：
接著，e指向key=7的節(jié)點劳澄，e!=null繼續(xù)執(zhí)行
next=e.next=3（線程2執(zhí)行完之后結(jié)構(gòu)發(fā)生了變化節(jié)點7指向了節(jié)點3）
e.next = newTable[i];節(jié)點7指向節(jié)點3（這時要看線程1的newTable）
newTable[i] = e;newTable[i]指向節(jié)點7
e = next地技；e節(jié)點指向下一個節(jié)點3
Entry<K,V> next = e.next e節(jié)點的下一個節(jié)點為null；
e.next = newTable[i];3節(jié)點的下一個節(jié)點指向節(jié)點7
newTable[i] = e;newTable[i]指向節(jié)點3秒拔；
e=next莫矗；e為空 結(jié)束循環(huán)；
這次擴容結(jié)束了砂缩。但是后續(xù)如果有查詢（無論是查詢的迭代還是擴容）作谚，都會hang死在table【3】這個位置上。同時庵芭，這個過程中發(fā)現(xiàn)節(jié)點5在線程1丟掉了妹懒，所以多線程下put，也可能造成元素丟失双吆。
Java1.8擴容
首先眨唬，看下hashMap中怎么計算key的hash值：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
圖中的 hash 是由鍵的 hashCode 產(chǎn)生会前。計算余數(shù)時，由于 n 比較小匾竿，hash 只有低4位參與了計算瓦宜，高位的計算可以認為是無效的。這樣導(dǎo)致了計算結(jié)果只與低位信息有關(guān)岭妖，高位數(shù)據(jù)沒發(fā)揮作用临庇。為了處理這個缺陷，我們可以上圖中的 hash 高4位數(shù)據(jù)與低4位數(shù)據(jù)進行異或運算昵慌，即 hash ^ (hash >>> 4)假夺。通過這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進行異或废离，以此加大低位信息的隨機性侄泽，變相的讓高位數(shù)據(jù)參與到計算中。此時的計算過程如下：
在 Java 中蜻韭，hashCode 方法產(chǎn)生的 hash 是 int 類型悼尾，32 位寬。前16位為高位肖方，后16位為低位闺魏，所以要右移16位。
下面重點講下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ù)時再進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果桶中不包含鍵值對節(jié)點引用析桥，則將新鍵值對節(jié)點的引用存入桶中即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果鍵的值以及節(jié)點 hash 等于鏈表中的第一個鍵值對節(jié)點時，則將 e 指向該鍵值對
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 {
// 對鏈表進行遍歷泡仗，并統(tǒng)計鏈表長度
for (int binCount = 0; ; ++binCount) {
// 鏈表中不包含要插入的鍵值對節(jié)點時，則將該節(jié)點接在鏈表的最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果鏈表長度大于或等于樹化閾值猜憎，則進行樹化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 條件為 true娩怎，表示當前鏈表包含要插入的鍵值對，終止遍歷
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判斷要插入的鍵值對是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 鍵值對數(shù)量超過閾值時胰柑，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
插入邏輯并不復(fù)雜截亦，下面看下擴容機制(一下內(nèi)容參考https://segmentfault.com/a/1190000012926722)：
在 HashMap 中，桶數(shù)組的長度均是2的冪柬讨，閾值大小為桶數(shù)組長度與負載因子的乘積崩瓤。當 HashMap 中的鍵值對數(shù)量超過閾值時，進行擴容踩官。
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) {
// 當 table 容量超過容量最大值，則不再擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按舊容量和閾值的2倍計算新容量和閾值的大小
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
/*
* 初始化時蔗牡，將 threshold 的值賦值給 newCap肾扰，
* HashMap 使用 threshold 變量暫時保存 initialCapacity 參數(shù)的值
*/
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/*
* 調(diào)用無參構(gòu)造方法時畴嘶，桶數(shù)組容量為默認容量，
* 閾值為默認容量與默認負載因子乘積
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 為 0 時集晚，按閾值計算公式進行計算
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ù)組偷拔，并將鍵值對映射到新的桶數(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)
// 重新映射時蒋院，需要對紅黑樹進行拆分
((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é)點按原順序進行分組
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é)點時莲绰，一般都是先通過模運算計算桶位置欺旧，接著把節(jié)點放入桶中即可,在 JDK 1.8 中，則對這個過程進行了一定的優(yōu)化
上圖中蛤签，桶數(shù)組大小 n = 16辞友，hash1 與 hash2 不相等。但因為只有后4位參與求余震肮，所以結(jié)果相等赴恨。當桶數(shù)組擴容后怀读，n 由16變成了32羹奉，對上面的 hash 值重新進行映射：
擴容后笔横，參與模運算的位數(shù)由4位變?yōu)榱?位。由于兩個 hash 第5位的值是不一樣沦偎，所以兩個 hash 算出的結(jié)果也不一樣疫向。上面的計算過程并不難理解，繼續(xù)往下分析豪嚎。
假設(shè)我們上圖的桶數(shù)組進行擴容搔驼，擴容后容量 n = 16，重新映射過程如下:
依次遍歷鏈表侈询，并計算節(jié)點 hash & oldCap 的值舌涨。如下圖所示
如果值為0，將 loHead 和 loTail 指向這個節(jié)點妄荔。如果后面還有節(jié)點 hash & oldCap 為0的話泼菌，則將節(jié)點鏈入 loHead 指向的鏈表中谍肤，并將 loTail 指向該節(jié)點啦租。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節(jié)點荒揣。完成遍歷后篷角，可能會得到兩條鏈表，此時就完成了鏈表分組：
最后再將這兩條鏈接存放到相應(yīng)的桶中系任，完成擴容恳蹲。如下圖：
從上圖可以發(fā)現(xiàn)虐块，重新映射后，兩條鏈表中的節(jié)點順序并未發(fā)生變化嘉蕾，還是保持了擴容前的順序贺奠。以上就是 JDK 1.8 中 HashMap 擴容的代碼講解。另外再補充一下错忱，JDK 1.8 版本下 HashMap 擴容效率要高于之前版本儡率。如果大家看過 JDK 1.7 的源碼會發(fā)現(xiàn)，JDK 1.7 為了防止因 hash 碰撞引發(fā)的拒絕服務(wù)攻擊以清，在計算 hash 過程中引入隨機種子儿普。以增強 hash 的隨機性，使得鍵值對均勻分布在桶數(shù)組中掷倔。在擴容過程中眉孩，相關(guān)方法會根據(jù)容量判斷是否需要生成新的隨機種子，并重新計算所有節(jié)點的 hash勒葱。而在 JDK 1.8 中浪汪，則通過引入紅黑樹替代了該種方式。從而避免了多次計算 hash 的操作错森，提高了擴容效率吟宦。
雖然jdk1.8中hashMap擴容避免了死循環(huán)，但是涩维，在并發(fā)情況下還是有可能取到空值的殃姓。
