Floating Cat

HashMap之哈希数组容量计算

字数统计: 1k阅读时长: 4 min
2016/09/21 Share

构造函数

HashMap在初始化时允许我们指定负载因子和哈希数组初始化容量大小,以JDK 1.8为例,其最终调用构造方法如下:

1
2
3
4
5
  public HashMap(int initialCapacity, float loadFactor) {
......
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

默认情况下负载因子loadFactory为0.75f初始化容量initialCapacity为16.

其中HashMap要求哈希数组的大小必须2n,如果我们在初始时指定initialCapacity为7会是如何?其处理逻辑在tableSizeFor()中,该方法用于返回大于输入参数且离它最近的2的整数次幂的数.比如对于参数7,那么最终哈希数组的大小为23,也就是8.

哈希数组容量计算

tableSizeFor()实现代码如下:

1
2
3
4
5
6
7
8
9
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;
}

先来看以下代码目的是什么:

1
2
3
4
5
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;

第一行代码是将n进行无符号右移1位,并将结果与右移前的n做按位或操作,最后把结果重新赋给n;后续操作类似.为了方便,通过一个例子来了解整个过程,我们随便取个数,只关注这个数高位的1即可.假设n对应的二进制数为:

1
1000 0000 0000 0000 0000 0000 0000 0000

第一行代码执行过后n变化过程如下,不难发现原本高位的1个1变成2个1.

步骤
n 1000 0000 0000 0000 0000 0000 0000 0000
n >>>1 0100 0000 0000 0000 0000 0000 0000 0000
n |= n >>> 1 1100 0000 0000 0000 0000 0000 0000 0000

第二行代码执行过后n变化过程如下,不难发现原本高位2个1变成4个.

步骤
n 1100 0000 0000 0000 0000 0000 0000 0000
n >>> 2 0011 0000 0000 0000 0000 0000 0000 0000
n |= n >>> 2 1111 0000 0000 0000 0000 0000 0000 0000

第三行代码执行过后n变化过程如下,不难发现原本高位4个1变成8个.

步骤
n 1111 0000 0000 0000 0000 0000 0000 0000
n >>> 4 0000 1111 0000 0000 0000 0000 0000 0000
n |= n >>> 4 1111 1111 0000 0000 0000 0000 0000 0000

第四行代码执行过后n变化过程如下,不难发现原本高位的8个1变成了16个.

步骤
n 1111 1111 0000 0000 0000 0000 0000 0000
n >>> 8 0000 0000 1111 1111 0000 0000 0000 0000
n |= n >>> 8 1111 1111 1111 1111 0000 0000 0000 0000

第五行代码执行后n的变化过程如下:

步骤
n 1111 1111 1111 1111 0000 0000 0000 0000
n >>> 16 0000 0000 0000 0000 1111 1111 1111 1111
n |= n >>> 16 1111 1111 1111 1111 1111 1111 1111 1111

此时我们发现32个bit已经全部被替换成了1.

步骤
原始 n 1000 0000 0000 0000 0000 0000 0000 0000
当前 n 1111 1111 1111 1111 1111 1111 1111 1111

现在执行n+1操作:

步骤
n 1111 1111 1111 1111 1111 1111 1111 1111
n + 1 0001 0000 0000 0000 0000 0000 0000 0000 0000

总结一下,该算法让最高位的1后面的位全变为1.比如10,11变为11;100,101,110,111变为111;最后再让结果n+1就可得到了2的整数次幂的值了.比如我们cap为7时,n就是7 - 1 = 6,对应二进制位为110,经过变换之后,n对应二进制位111,对n进行加1操作后,n对应的二进制位1000,即十进制8.

回过头来看第一条语句:

1
int n = cap - 1;

为了方便理解,直接来看个例子.假设当前输出参数cap为8,其二进制1000,如果不对它减1而直接操作,将得到答案10000,即16.显然不是预期结果.cap进行减1后二进制为111,再进行操作则会得到原来的数值1000,即8.总结下来就是避免对参数自身已经是2n的情况导致计算出错.

CATALOG
  1. 1. 构造函数
  2. 2. 哈希数组容量计算