1 HashMap 結(jié)構
-
底層數(shù)據(jù)結(jié)構进宝，1.7 和 1.8有什么不同
??① 1.7 數(shù)組 + 鏈表堡妒， 1.8 數(shù)組 +（鏈表 | 紅黑樹）
-
為何要用紅黑樹呼股，為何不一上來用紅黑樹，紅黑樹化的閾值為何是 8 刷喜，何時會樹化财喳，何時會退化為鏈表察迟？
?① 紅黑樹用來避免Dos攻擊，避免鏈表超長時性能下降耳高，樹化應當是偶然情況
??1） hash 表的查找扎瓶，更新的時間復雜度是O(1)，而紅黑樹的查找泌枪，更新的時間復雜度是O(log??)概荷，TreeNode 占用空間也比普通Noed的大，如非必要工闺，盡量還是使用鏈表
??2）hash 值如果足夠隨機乍赫，則在hsah表內(nèi)按泊松分布，在負載因子0.75的情況下陆蟆，長度超過8的鏈表出現(xiàn)概率是0.00000006雷厂，選擇8就是為了讓樹化幾率足夠小
?② 樹化兩個條件: 鏈表長度超過樹化閾值；數(shù)組容量>=64
?③ 退化情況1：在擴容時如果拆分樹時叠殷，樹元素個數(shù)<=6則會退化鏈表
?④ 退化情況2：remove 樹節(jié)點時改鲫，若root、root.left林束、root.right像棘、root.left.left有一個為空null，也會退化為鏈表
-
索引如果計算壶冒？hashCode都有了缕题，為何還要提供hash()方法？數(shù)組容量為何是2的n次冪胖腾？
?① 計算對象的hashCode(),再進行調(diào)用HashMap的hash()方法進行二次哈希烟零，最后 &(capacity-1) 得到索引
?② 二次hash()是為了綜合高為數(shù)據(jù)瘪松，讓哈希分布更為均勻
?③ 計算索引時，如果是2的n次冪可以使用位與運算代替模式锨阿，效率更高宵睦；擴容時hash & oldCap == 0的元素留在原來位置，否則新位置 = 舊位置 + oldCap（舊的容量）
?④ 但 ①墅诡、②壳嚎、③都是為了配合容量為2的n次冪時的優(yōu)化手段，例如Hashtable的容量就不是2的n次冪末早，并不能說哪種設計更優(yōu)烟馅，應該是設計者綜合了各種因素，最終選擇了使用2的n次冪作為容量
