java8 HashMap之tableSizeFor

2018-10-16 755 words 2 minutes views

在1.8的HashMap中,有一个算法,它的功能是（不考虑大于最大容量的情况） 返回大于输入参数且最近的2的整数次幂的数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    /**
     * Returns a power of two size for the given target capacity.
     */
    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 |= n »> 1;也等价于 n = n | (n »>1);

我们假设 cap = 65;

1
2
3
4


    int n = cap - 1  // 即 n = 64 (1000000 二进制)
    n |= n >>> 1;    // 即 n = n | (n >>> 1) = 1000000 | 0100000 = 1100000
    n |= n >>> 2;    // 即 n = n | (n >>> 2) = 1100000 | 0011000 = 1111000
    n |= n >>> 4;    // 即 n = n | (n >>> 4) = 1111000 | 0001111 = 1111111

再往下执行的话都是 n 的值都为1111111 即127 最后一步,就是一个嵌套的三元运算当n < 0,就返回1,否则继续判断n是否超过最大容量,没超过就返回 n + 1 即 n= 128 对比我们的输入值 –> 大于65且最近的2的整数次幂的数就是128

其实抛除上面这个具体的例子,整个过程可总结如下:

先来假设n的二进制为01xxx…xxx。接着
对n右移1位：001xx…xxx，再位或：011xx…xxx
对n右移2为：00011…xxx，再位或：01111…xxx
此时前面已经有四个1了，再右移4位且位或可得8个1
同理，有8个1，右移8位肯定会让后八位也为1。
综上可得，该算法让最高位的1后面的位全变为1。
最后再让结果n+1，即得到了2的整数次幂的值了。

这样就很清晰明了了,至于为什么最开始

-int n = cap - 1;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。

位运算是相当高效的。