2021-05-17 14:59发布
因为 n 永远是2的次幂,所以 n-1 通过 二进制表示,永远都是尾端以连续1的形式表示(00001111,00000011)当(n - 1) 和 hash 做与运算时,会保留hash中 后 x 位的 1
好处:
&运算速度快,至少比%取模运算块
能保证 索引值 肯定在 capacity 中,不会超出数组长度
(16-1)&hash,计算的索引会落在[0,15],不会越界 ,与运算的结果取决于hash值,这样只要保证hash是均匀散列的,也就是保证1均匀分布就能防止索引冲突。
最多设置5个标签!
因为 n 永远是2的次幂,所以 n-1 通过 二进制表示,永远都是尾端以连续1的形式表示(00001111,00000011)当(n - 1) 和 hash 做与运算时,会保留hash中 后 x 位的 1
好处:
&运算速度快,至少比%取模运算块
能保证 索引值 肯定在 capacity 中,不会超出数组长度
(16-1)&hash,计算的索引会落在[0,15],不会越界 ,与运算的结果取决于hash值,这样只要保证hash是均匀散列的,也就是保证1均匀分布就能防止索引冲突。
一周热门 更多>