当前位置：网站首页>为什么hash%length==hash＆(length-1)的前提是 length 是 2 的 n 次方

为什么hash%length==hash＆(length-1)的前提是 length 是 2 的 n 次方

2022-04-23 12:02:00 【滕青山YYDS】

Hash值的范围在-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，但是我们不可能去创建一个40亿大小的数组，HashMap的默认数组大小是16。

所以在拿到Hash值之后需要对数组长度进行取余，得到的余数就是在数组的索引位置。

那么为什么说hash%length == hash&(length-1)的前提是 length 是 2 的 n 次方？

从二进制的角度来看，对一个数右移1位就是除以2，它剩余的二进制数字所表示的就是除以2得到的结果，那么被移出的数字就是余数。
也就是说，对一个数右移n位，就是让这个数除以2的n次方，被移出的n位数字就是我们想要的余数。

当数组的长度是2的n次方的时候，我们让hash对它取余就是想要hash的最右边的n位数。
此时，数组的长度在二进制的数字表示就是1后面跟着n个0，如果对它-1，也就是length-1，此时二进制的数字表示就是前面都是0，后面跟着n个1。
那么我们就让hash跟length-1进行位与运算，也就得到了hash的后n位也就是想要的余数。

之所以采用hash&(length-1)来取余，而不是直接进行hash%length的原因在于：位运算计算速度更快，更加高效。

参考：
Java集合常见知识点&面试题总结(下) | JavaGuide
二进制按位与&及求余数 | Perkins4j2的技术博客

版权声明
本文为[滕青山YYDS]所创，转载请带上原文链接，感谢
https://tengqingshan.blog.csdn.net/article/details/124360052

边栏推荐

猜你喜欢

随机推荐