HashMap中的roundUpToPowerOf2()和tableSizeFor()

桃扇骨 2022-12-30 07:59 102阅读 0赞

**目录**

1.roundUpToPowerOf2()和tableSizeFor()是什么

2.roundUpToPowerOf2()方法解析

3.tableSizeFor()方法解析

--------------------

### 1.roundUpToPowerOf2()和tableSizeFor()是什么 ###

**roundUpToPowerOf2()：**JDK1.7中HashMap初始化时的一个方法，目的为：**返回大于或等于最接近输入参数的2的整数次幂的数**

**tableSizeFor()：**JDK1.8中HashMap构造函数中用于初始化扩容阈值threshold的一个方法，其目的同上：**返回大于或等于最接近输入参数的2的整数次幂的数**

### 2.roundUpToPowerOf2()方法解析 ###

roundUpToPowerOf2()方法源码：

![20201224143527666.png][]

可以看到主要是调用了Integer.highestOneBit方法，这个方法有什么用呢？我们做个简单的测试：

![20201224143751907.png][]

![20201224143758994.png][]

可以看到这个方法可以返回的是比当前元素小的2的次方数，究竟是怎么实现的呢，先思考下如果让我们来写会怎么写？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70][]

笔者随手一挥就码出了一个O(n^2)的函数（哈哈哈，菜的让人想笑。。。）当然JDK的开发者不能这么去写，所以我们看一下JDK是怎么实现的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1][]

我们就拿15举例，看一下这个函数是怎样输出8的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2][]

我们再换一个数，这次假设最高位为第5位，后四位用\*代替（意思为任意值）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3][]

通过结果我们可以发现，这些或运算的目的为：**除最高位外，把其他位都填充为1，这样最后再把这个值右移一位做差，即可计算出比输入元素小的2的次方数。**好的这个方法解释清楚后我们再往上看，看**Integer.highestOneBit((number - 1) << 1)**这行代码，左移一位很容易理解，因为我们最终目的要得到的是**返回大于或等于最接近输入参数的2的整数次幂的数，**既然我们已经得到了**比输入元素小的2的次方数，再乘个2就OK了。**但这里要注意一种情况就是，**如果我们输入的值就是2的n次方呢？**如果直接把参数带入的话会出现输入的值是8，但实际返回的是16。所以才需要把**number - 1，这样即可以保证无论输入的是不是2的次方数，输出的都为大于或等于最接近输入参数的2的整数次幂的数。至于为什么要位移到16位，是因为int为4字节占32位，所以移动16位即可把高16位全部移动完。**

### 3.tableSizeFor()方法解析 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4][]

理解了1.7中的roundUpToPowerOf2()方法后，1.8中的tableSizeFor()对roundUpToPowerOf2()方法进行了优化，只不过实现上有些许不同。`>>>`和`|`的操作的目的还是为了**把n从最高位的1以下都填充为1**，**最高位及其以下的都为1，这样就能保证得到的结果肯定大于或等于原来的n且为奇数，最后再加上1，即为：大于且最接近输入值的2的整数次幂的数**。写的有些简单，这里就不再贴图去解释了，有兴趣的小伙伴可以画一下图，画完秒懂。

[20201224143527666.png]: /images/20221120/3f5f6697ee064cd6a5c0dc72b1fe6f22.png
[20201224143751907.png]: https://img-blog.csdnimg.cn/20201224143751907.png
[20201224143758994.png]: https://img-blog.csdnimg.cn/20201224143758994.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201224144734379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201224145034114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201224150304911.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201224150932108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020122415203830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70