HashMap 的长度为什么是 2 的幂次方？
不知名程序员韭菜2020-07-05 00:40
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。
为什么取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作？
我们知道，2的幂次在使用二进制表示时，第一位总是1，而剩下的都为0，如：
4-->100
8-->1000
16-->10000
按位与操作，只有当2个都为1是，才为1，否则为0。
而2 的幂次-1，在二进制中表示都为1，如16-1=15表示为1111，意思就是说将比余数小的低位数字全都保留，而比余数高的全都抛弃。
取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作的原理就是将高位抛弃，低位留下。
我们以13%8为例
13的二进制为 1101
8-1=7的二进制为 111
按位与的结果为 101
将结果转换为十进制5，13%8=5，结果正确。
举报/反馈
0
0
收藏
分享
