寫在前邊
- HashMap屬于比較常用的資料結構了，面試過程中也經常會被問到，本篇就知識點，展開問答式分析，重點聊聊hash沖突、擴容死鍊、容量為2的n次方等問題~
1.7和1.8有什麼不同
1.7是 數組+連結清單 1.8是 數組+連結清單【超過門檻值會變成紅黑樹】
如何解決Hash沖突問題
擴容
條件
- 連結清單長度超過8
- 元素個數超過數組個數的75%
樹化規則
條件
- 連結清單長度超過8
- 此時看看數組長度是否超過64，超過就進行樹化，否則隻是單純擴容
為什麼需要樹化
其實一般正常的元素，都是不會超過門檻值的，隻有插入一堆重複的元素，hash值一樣，才可能達到門檻值，這個簡稱Dos攻擊 而元素一旦多起來，連結清單查找的效率就遠不及紅黑樹了
♂️樹化一定更好嗎？
不是的，維護紅黑樹需要占用比連結清單更多的空間，而且當連結清單長度足夠短的時候，連結清單查找的效率反而比紅黑樹更高？？
為什麼選擇0.75和8
- hash 值如果足夠随機，則在 hash 表内按泊松分布，在負載因子 0.75 的情況下，長度超過 8 的連結清單出現機率是 0.00000006，樹化門檻值選擇 8 就是為了讓樹化幾率足夠小
退化規則
擴容的時候連結清單長度<=6
remove節點的時候
root、root.left、root.right、root.left.left 有一個為 null ，也會退化為連結清單（看的是移除之前的情況）
為什麼需要二次哈希
先獲得key的hashCode的值 h，然後 h 和 h右移16位 做異或運算。
實質上是把一個數的末x位低16位與他的高16位做異或運算，因為在前面 (n - 1) & hash 的計算中，hash變量隻有末x位會參與到運算。使高16位也參與到hash的運算能減少沖突
為什麼要用2的n次方
為了友善 & 操作
隻有2的n次方，去-1，才能用 & 替代 %
為了友善擴容
擴容時重新計算索引效率更高： hash & oldCap == 0 的元素留在原來位置 否則新位置 = 舊位置 + oldCap （oldCap：原始的容量）
因為HashMap的初始容量是2的次幂，擴容之後的長度是原來的二倍，新的容量也是2的次幂，是以，元素，要麼在原位置，要麼在原位置再移動2的次幂。
看下這張圖，n為table的長度 圖a表示擴容前的key1和key2兩種key确定索引的位置 圖b表示擴容後key1和key2兩種key确定索引位置。
元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，是以新的index就會發生這樣的變化：
是以在擴容時，隻需要看原來的hash值新增的那一位是0還是1就行了【直接 hash & oldCap，就能知道是0還是1了】 是0的話索引沒變，是1的話就變成原索引+oldCap
不用2的n次方可以嗎
可以的，因為2的n次方也會有缺陷，比如給定的值全是偶數，無論如何hash之後取模，都是偶數，分布就不均勻
此時如果用質數作為容量的話，就會分布得比較均勻
注意
二次 hash 是為了配合 容量是 2 的 n 次幂 這一設計前提，如果 hash 表的容量不是 2 的 n 次幂，則不必二次 hash
容量是 2 的 n 次幂 這一設計計算索引效率更好，但 hash 的分散性就不好，需要二次 hash 來作為補償，沒有采用這一設計的典型例子是 Hashtable
并發擴容丢失資料問題
主要是第一個節點才會吧？因為第一個是new Node出來的
jdk1.7 并發擴容死鍊問題
jdk1.7中，采用的是頭插法，用一個e指針表示目前要擴容的節點，next表示接下來要擴容的節點，一直頭插e更新e為next，直到e為null
假設現在有兩個線程1和2，要擴容一個Map
- 線程1的局部變量e，指向了a節點，next指向b節點
- 線程2的局部變量也是如此，此時線程2先進行擴容，由于是頭插法，最終結果變成了 b->a
- 但此時來到線程1先進行，局部變量不會受改變，e還是指向a，next還是b，是以把a頭插，并且更新e為next，也就變成了b
- 線程1繼續頭插b，沒問題，結果變成了[b->a]，看起來是沒問題了，但是接下來判斷e還沒有next：
- 發現e的next是a，又要繼續頭插a，插完a之後，發現a的next又是b，寄了這下，無限循環了
原文連結：https://juejin.cn/post/7160661444143841288