HashMap源码__tableSizeFor方法解析

tableSizeFor（int cap）方法返回不小于指定参数cap的最小2的整数次幂，具体是怎么实现的呢？看源码！

    /**

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

    }

1）为什么cap要减一？

2）|=是什么？

3）>>>又是什么？

4）为什么要返回n+1

先解释一下"|"是什么

这里的“|”是叫做位或运算，百度百科这样解释到：按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的2个二进位有一个为1时，结果位就为1。当参与运算的是负数时，参与两个数均以补码出现。

假设使用8位来储存数字，下面用一张图来说明下位或运算： 8|1

十进制8的二进制表示为图中的A ： 00001000

十进制1的二进制表示为图中的B ： 00000001

从图中可以看出A从右向左第四个位为1，B从右向左第一个位为1，其余位都为0，因此结果的第一个和第四个位都为1，结果就是00001001转换为十进制就是9，因此 8 | 1 = 9 。

A |= B 的意思就是 A = A | B

>>>表示无符号右移

也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。

假设使用8位来储存数字，下面用一张图来说明下右移运算： 8>>>1

8>>>1表示将8右移一位，如图所示：右移后高位也就是蓝色部分补0，低位也就是红色部分直接舍弃，结果就变成了0000100转换为十进制就是4，因此 8 >>> 1 = 4

明白了>>>和 | 的作用就可以来解释上面的源码了，

假设cap=9，n = cap - 1 = 8（至于为什么需要减一待会儿再说）

n |= n >>> 1; 也就是 n = n | (n>>>1)
在java中int占4个字节也就是32位，

因此8的二进制表示为：00000000......00001000 （中间省略16个0）
8>>>1的结果是： 00000000......00000100
8 |= 8>>>1 的结果是： 00000000......00001100

结果转换为十进制为：12

12>>>2的结果是：00000000......00000011
12 |= 12>>>1的结果是：00000000......00001111

结果转化为十进制为：15

15>>>4的结果是：00000000......00000000
15 |= 15>>>4的结果是：00000000......00001111

结果转化为十进制为：15

15>>>8的结果为：00000000......00000000
15 |= 15>>>8的结果为：00000000......00001111

结果转化为十进制为：15

15>>>16的结果为：00000000......00000000
15 |= 15>>>16的结果为：00000000......00001111

结果转化为十进制为：15　　

最后返回 n+1 也就是 16

上面的操作其实就是把 8 的二进制表示 00000000......00001000，把 1 后面的 0 全部变成了000000000......0001111.

为什么 n+1 之后就是2的整数次幂呢?

看一下二进制是如何转换为十进制的就明白了

二进制转换为十进制:

设一个n位的二进制的位数从右至左依次为0~n位，那么从0~n位分别乘于2的n次幂的和即为该二进制的十进制形式。

00000001 的十进制表示为 1 * 2^0 = 1

00000001 加一之后就变成了 00000010 转换为十进制就是 0*2^0 + 1*2^1 = 0 + 2 = 2

00000011 的十进制表示为 1*2^0 + 1*2^1 = 3

00000011 加一之后就变成了00000100 转换为十进制就是 0*2^0 + 0*2^1 + 2*2^2 = 0 + 0 + 4 = 4

00000111 的十进制表示为 1*2^0 + 1*2^1 + 1*2^2 = 7

00000111加一之后就变成了00001000 转换为十进制就是 0*2^0 + 0*2^1 + 0*2^2 + 1*2^3 + = 0 + 0 + 0 + 8 = 8

为什么要对cap进行减一操作呢?

这样就可以避免当cap已经是2的整数次幂时,再对cap进行一次求次幂操作,比如:cap=16,如果没有减一结果就会变成32,而16已经符合HashMap的要求了.

巴特西

HashMap源码__tableSizeFor方法解析

先解释一下"|"是什么

>>>表示无符号右移

为什么 n+1 之后就是2的整数次幂呢?

二进制转换为十进制:

为什么要对cap进行减一操作呢?

最新文章

热门文章