1. 實現(xiàn)原理
解決哈希沖突（哈希碰撞）的辦法有很多准给，例如開放定址法、再散列函數(shù)法、鏈地址法等，HashMap采用的是鏈地址法败京。因此HashMap的底層是數(shù)據(jù)+鏈表的結(jié)構(gòu)。
從性能考慮互订，對鏈表的操作時間復雜度是O(n)叠赦，因此HashMap中的鏈表出現(xiàn)的越少，性能才會越好牲蜀。
兩個概念：capacity容量：默認值16笆制；loadFactor加載因子：默認值0.75。
2. 幾個問題
1. 為何HashMap的數(shù)組長度一定要是2的次冪涣达？
方便擴容后的resize操作在辆。擴容后只有一位差異，方便快速更新擴容后的位置度苔。
2. 為什么Map桶中個數(shù)超過8個才轉(zhuǎn)為紅黑樹匆篓？
桶中元素初始化是鏈表保存的，鏈表查找的時間復雜度是O（n）寇窑，而紅黑樹的查找性能為O(log(n))鸦概。當鏈表長度很小時，遍歷速度快甩骏，但鏈表長度增加后對查詢性能有一定影響窗市，因此引入TreeNode。
tips：TreeNode是類似于TreeMap的結(jié)構(gòu)横漏，底層是紅黑樹谨设。單個TreeNode需要占用的空間約是普通Node的兩倍。
當鏈表長度達到8則轉(zhuǎn)成紅黑樹缎浇，但當紅黑樹的節(jié)點數(shù)降低到小于等于6時則恢復為鏈表形態(tài)扎拣。說白了就是時間和空間的平衡思想。
當hashcode離散型良好的時候，樹型bin用到的概率非常小二蓝，因為數(shù)據(jù)均勻的分布在每個bin中誉券，幾乎不會有bin種鏈表長度達到閾值。但在隨機hashcode下刊愚，離散性可能變差踊跟，因此就可能導致不均勻的數(shù)據(jù)分布。不過理想情況下鸥诽，鏈表長度符合泊松分布商玫，一個鏈表長度達到8個元素的概率為0.00000006低于千萬分之一。
事實上牡借，鏈表長度超過 8 就轉(zhuǎn)為紅黑樹的設計拳昌，更多的是為了防止用戶自己實現(xiàn)了不好的哈希算法時導致鏈表過長，從而導致查詢效率低钠龙，而此時轉(zhuǎn)為紅黑樹更多的是一種保底策略炬藤，用來保證極端情況下查詢的效率。
3.資料擴充
-
解決hash沖突中的開放定址法
當發(fā)生地址沖突時碴里，按照某種方法繼續(xù)探測哈希表中的其他存儲單元沈矿，直到找到空位置為止。注意對于利用開放地址法處理沖突所產(chǎn)生的哈希表中刪除一個元素時需要謹慎咬腋，不能直接地刪除羹膳，因為這樣將會截斷其他具有相同哈希地址的元素的查找地址，所以帝火，通常采用設定一個特殊的標志以示該元素已被刪除溜徙。
