HashMap中tableSizeFor方法解析

HashMap中有一个计算大于等于cap且结果为2的N次方整数的方法tableSizeFor。

这个方法使用了位运算,有点巧妙,在这里简单解析一下原理:

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;
}

先分析一下2的N次方整数的二进制有什么特点?
1、二进制表示下,只有一位是1,其他的都是0。
2、假设需要计算的数为n,结果又可以表示为,n的最高位1开始往右(地位),全部变成1之后的值,再加上1。

举个例子,假设n为10,则n的2进制为:

0000 1010

从最高位1开始往右全变1得:

0000 1111

再加1得:

0001 0000

十进制结果为16,也就是结果值。

其中代码中的n |= n >>> 1;这几行做的事就是为了变1,具体怎么变往后再说,先看一下为啥n要等于cap-1。
假设给定的cap已经是2的N次方了,这个时候如果不-1,按照逻辑变1之后再加1,结果就会变成2倍的cap了,也就与应有的结果不一致,也就是因为要处理这种特殊情况,所以需要先执行n=cap-1的操作。

n |= n >>> 1;这几行,这几行是变1的核心。
原理是,将n的值右移1位,这个时候比1低一位的值也变成了1,然后进行一下或运算,即可得到2位1。
这个时候因为已经可以保证高位前2位是1了,所以可以继续右移2位继续进行或运算,可以得到4位1。
依葫芦画瓢,高位前4位是1,继续右移或运算,直到n |= n >>> 16;结束。(因为int是32位的,所以执行到16即可)
说起来比较抽象,拿n=8举例就可以比较清楚的看懂原理。

n=8;            //0000 1000
n |= n >>> 1;   //0000 1000 | 0000 0100 = 0000 1100
n |= n >>> 4;   //0000 1100 | 0000 0011 = 0000 1111
n |= n >>> 8;   //0000 1111 | 0000 0000 = 0000 1111
n |= n >>> 16;  //0000 1111 | 0000 0000 = 0000 1111

因为在计算机系统中,位运算非常的快,所以通过这个方法的算法即可快速的得到想要的值,还是挺巧妙的,学习了一波。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍