HashMap为什么数组长度是2的幂
首先，先说结论：主要是为了在取模和扩容时做优化
- 简化取模运算：将
a%length转换成a&(length-1)，位运算更快- 扩容的时候我们需要重新计算元素在新数组中的位置，此时我们不需要再次哈希取余，元素在新数组的索引就在：
原索引或者原索引+原数组容量本文主要解答为什么数组长度是2的幂时可以将
a%length转换成a&(length-1)
-
例如
a=105=0110 1001，b=16=0001 0000，可以看到2的幂二进制表示只有一个1 -
取余操作本质是：
a%b=a-b*c，这个c指的是b倍乘c后不超过a的最大数 -
此时只需要确定
c就能求出余数，而二进制中往左移一位就表示扩大两倍，那么如果b的二进制表示只有一个1其他全是0的话：- 此时a的二进制表示中对应b这个1所在的那一位开始往左的数中：
- 只有一个1，那么就可以知道b左移x次就能得到，即
c=x*2，此时余数就是a中往右的二进制，例如a=0100 1001,b=0001 0000，此时c=4,余数是1001 - 有多个1，例如
a=0110 1001,b=0001 0000，此时c=2*1 + 2*2，那么余数也是1001
- 只有一个1，那么就可以知道b左移x次就能得到，即
- 此时a的二进制表示中对应b这个1所在的那一位开始往左的数中：
-
由此可知，当
a%b的时候如果b的二进制表示中只有一个1，那么余数就是a中对应b这个1所在位右边的二进制表示的数- 那么如何计算能使
a=0110 1001得到0000 10010000 1001 = 0110 1001 & 0000 1111 = a % (b-1)
- 那么如何计算能使