记jdk1.8中hashmap的tableSizeFor方法

2019-08-09 00:00:00 hashmap 方法 jdk1

 

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

 下面是官方注释:

Returns a power of two size for the given target capacity.   百度翻译:(返回给定目标容量的二次幂。)

也就是获取比传入参数大的最小的2的N次幂。
比如:传入8,就返回8,传入9,就返回16.
为什么要用这个方法呢?
MAXIMUM_CAPACITY常量上有这么一句注释:MUST be a power of two <= 1<<30
就是容量必须是2 的n次冥。而且最大容量是2的30次方。
这几涉及到hashmap的Node<K,V>[]角标的问题了,我们都知道hashmap首先是存到一个数组中的,也就是Node<K,V>[]中,如果想要传入的key均匀的分布到这个数组中,
就需要hashmap的容量是2的N次冥了。
具体的可以看看https://blog.csdn.net/a_long_/article/details/51594159这篇文章。


下面我们来说说这个方法为什么可以获取到2的N次冥把。

首先要了解 | 和 >>> ,这个不懂的可以自己百度,很简单。
n |= n >>> 1;
n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;

首先看这集行有什么作用呢,他就是我了的到一个二进制数,这个二进制数前面都是0,后面都是1,组成。
比如:00001111。 这个数是十进制15,那么这个数+1的话很容易的就得到了16,也就是2的4次冥。
那为什么这个算法可以得到这种结构呢?
让我们来举个例子,因为hashmap最大容量是2的30次方,那么我们就那2的30次方来举例。
n = 2^30 转换成2进制: 01000000000000000000000000000000

n |= n >>> 1 : 01100000000000000000000000000000
n |= n >>> 2      :  01111000000000000000000000000000
n |= n >>> 4      :  01111111100000000000000000000000
n |= n >>> 8      :  01111111111111111000000000000000
n |= n >>> 16     :  01111111111111111111111111111111

先不管最大位是符号位的问题,2^30通过这样计算以后得到的就是一个2^31-1的数,然后再+1就得到了2^31次了,

所以这个公式得到的就是n后面的2的n次冥了。

那么如果传入的n正好是像2^30次一样呢,那么直接用这个方法就会得到2的31次冥了,所以有了开始的
int n = cap - 1;

这样我们通过这个方法就肯定能得到2的n次冥了。





    

相关文章