Question

hashmap初试数组大小为什么一定要是2 的倍数

Answer 1

1、在hashmap 的底层源码中，首先会计算一个 key 的 hash 码，比如计算一个字符串 "1".hashcode(); 会得到 hashcode 的大小为 49，但是 hashmap 默认数组的大小是 16，所以这样肯定是不能存到数组里面的，会越界
2、需要再次通过一个 hash 函数（这个hash 函数是自己定义的）来得到一个 hash 值，在 hashmap 的底层，这个 hash 函数是用 hashcode 的低 16 位与 高16 位进行的一次异或运算如下：

为什么要进行这一步的运算呢？看下面：
这就是HashMap的高明之处。先看个例子，一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。那这样有什么意义呢？看第3步。
3、 得到h之后，把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。还有一点需要说明，HashMap的键可以为null，它的值是放在数组的第一个位置。

3、得到 hash 值之后，再与数组的长度-1（length-1）进行一次与运算，因为如果数组的长度是 2 的倍数，那么length-1 的二进制一定是 ...00001111...这种形式，也就是前面一定都是 0，后面全是1，那么再与 hash 值进行与运算的时候，结果一定是在原来数组大小的范围内，比如默认数组大小16-1=15 的二进制为： 00000000 00000000 00000000 00001111，某 key 的hash 值为：11010010 00000001 10010000 00100100，那么与上面做与运算的时候，值会对后面的四位进行运算，肯定会落在0~15 的范围内，假如不是 2 的倍数，那么 length-1 的二进制后面就不可能全是 1，做与运算的时候就会造成空间浪费