JDK HashMap幾個有意思的問題

## HashMap的hash算法

 hash源碼如下

 做了什麼？

• 擷取hash值
• hash值無符号右移
• 然後把前兩步的結果做亦或運算

  為啥這麼做？

•  經過上邊的操作，右移 和 亦或運算。得到的hash值二進制的高十六位和低十六位将都保留hash值的數字特征。
• 另外，也和hash尋址有關，按照正常的邏輯，我們想要把hash值對數組長度取模，然後當做數字下标。而源碼進行了優化，通過 （n-1）& hash 值得到下标，其實一樣的效果，這不過這樣的效果更好一點 。
• 再根據上邊的hash尋址，位移，和亦或，可以減少hash沖突。

## Hash碰撞怎麼做（hash沖突）

  連結清單+紅黑樹

  如果元素的key的hash值相同，則使用一個連結清單來存放。連結清單查找一個元素的時間複雜度為 O（n），連結清單到達一定長度（8），則使用紅黑樹，紅黑樹尋找一個元素的時間的時間複雜度為O（logn）

## rehash 擴容 

 當存放的長度到達門檻值以後，就要出發rehash，将原來的進行重新hash，判斷hash值和新的數組長度與的結果，是否多了一個比特，如果沒多則還是原來的位置，如果多了，則是原來的位置 + 原來的數組的長度，就是在新數組的下标位置。