记jdk1.8中hashmap的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;
}

　下面是官方注释：

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次冥了。

　　　　

原文链接:https://www.cnblogs.com/maylong/p/11232086.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有