為了能讓 HashMap 存取高效,盡量較少碰撞,也就是要盡量把數據分配均勻,每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的算法。
這個算法應該如何設計呢?
我們首先可能會想到采用%取余的操作來實現。但是,重點來了:“取余(%)操作中如果除數是2的冪次則等價于與其除數減一的與(&)操作(也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二進制位操作 &,相對于%能夠提高運算效率,這就解釋了 HashMap 的長度為什么是2的冪次方。
那為什么是兩次擾動呢?
這樣就是加大哈希值低位的隨機性,使得分布更均勻,從而提高對應數組存儲下標位置的隨機性&均勻性,最終減少Hash沖突,兩次就夠了,已經達到了高位低位同時參與運算的目的;