HashMap中, 不管容量参数是多少, 最终容量都会被重新计算, 按照大于等于输入参数且最小的2的整数次幂的数.
例如: 参数是9, HashMap内部的计算后的容量会是16.
今天就一起看下HashMap为什么要这样设计, 又有哪些地方是值得我们借鉴思考的.
容量计算
HashMap中使用tableSizeFor()方法, 计算参数对应容量值, 即大于等于参数且最小的2的整数次幂的数.
容量计算方法:
代码语言：javascript复制static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}这个方法中所有 ”|=” 计算的目的就是利用或( | )运算,
将数字n(二进制)的第一个值为1的数位的右边所有位都变为1.
例如:
代码语言：javascript复制0000 1001
-->
0000 1111下面就以数字9为例,一起看下具体的执行过程
1. 右移一位, 并或(|)计算
代码语言：javascript复制n |= n >>> 1;
// 执行如下:
n>>>1 = 0000 1001 >>>1 = 0000 0100
n = n|n>>>1 = 0000 1001 | 0000 0100 = 0000 11012. 右移两位, 并或(|)计算
代码语言：javascript复制n |= n >>> 2;
// 执行如下:
n>>>2 = 0000 1101 >>>2 = 0000 0011
n = n|n>>>2 = 0000 1101 | 0000 0011 = 0000 1111方法执行到这已经很明显了, 原有最高位为1的右边都已经变为1了.
3. 求大于等于入参的最小2的n次幂
在不超过最大容量时, 执行n 1计算容量值, 即得大于等于入参的最小2的n次幂.
代码语言：javascript复制n 1 = 0000 1111 1 = 0001 0000 = 16;这也是方法第一行中先减一的原因, 就是为了保证找到的目标值大于或等于参数.
代码语言：javascript复制int n = cap-1;所以当初始化容量长度的入参为9时, 实际是需要定义长度为16的数组.
为什么容量为2的n次幂
在HashMap中, 容量的本质就是hash桶, 每个key会对应到一个hash桶中, 所以能快速定位是非常必要的.
一般的hash逻辑都是取模(%)处理,
但HashMap中都是使用与(&)操作进行快速定位的.
具体代码在put()和get()中都有:
代码语言：javascript复制p = tab[i = (n -1) & hash]这样做的优点是:1.与(&)操作的效率比取模(%)的执行效率高;
2.(n - 1) & hash的值是均匀分布的, 能够减少hash冲突;
而容量为2的n次幂的原因是
当n为2次幂时, (n - 1) & hash = hash % n
启示
1.同样需求下, 使用位操作计算效率会高很多, 开发中应当尽量使用;
2.HashMap中的hash算法, 在分库分表等分片场景中都可以参考使用, 是非常有借鉴意义的.
