服务器之家

服务器之家 > 正文

Java源码解析HashMap的tableSizeFor函数

时间:2021-06-30 14:42     来源/作者:李灿辉

aka,hashmap的容量大小必须为2的指数,即16,32,64,128这样的值。那么,在构造函数中,如果调用者指定了hashmap的初始大小不是2的指数,那么,hashmap的tablesizefor函数,会计算一个大于或等于给定参数的2的指数的值。先来看一下tablesizefor函数的源码,如下

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

这里采用的计算方法不太常见。先是对cap-1,然后一直进行右移操作,最后根据n和maximum_capcity的大小关系,返回一个值。这究竟是如何实现找到一个大于或等于cap的2的指数的值呢?

首先需要解释一下>>>符号。>>>是无符号右移操作,即,右移后,高位补0. 例如二进制的11000101,>>>1后,得到01100010,即不关心符号位,右移后,高位直接补充0. 

还有一个符号是|=,例如n |= n>>>1,这个其实可以翻译为n = n | n>>>1,| 是位或操作,即两个数字按位进行或操作,即,某一位上,只有一个数字的该位为1,该位的结果即为1.

说清楚了两个符号的含义,下面我们开始解释算法的过程。

函数一开始,把cap -1 赋值给n。这里我们先按住不说,稍后回头解释。接下来就是对n的四次变换。举个例,对于

01010000

这个值来说,n>>>1即可得到

00101000

两个数字位或后,得到

01111000

可以这么来看这个事情,最开始的n,总有它的最高位为1. 右移1位后,与n进行位或操作,则结果的最高位和次高位都为1了,也就是得到了2个1,而且是高位的2位都为1了。

那么这时再对n进行n>>>2,再和n进行位或操作,即可得到4个1. 依此类推,n |= n>>>4,即可得到8个1。然后n |= n>>>8,即可得到16个1。然后 n |= n>>>16,即可得到32个1. 当然,后面几步得到多少个1,得需要n的初始值足够大才可以。否则,n右移后可能就位0了,那么在进行位或操作,也只是上一步的值而已。

通过上面的分析,可以知道,进行完n的四次右移然后位或操作后,得到的其实是n的所有为都为1的一个值。那么最后,返回的时候,取的n + 1,那么即可得到一个比n大的2的指数的值。

那么回过头来看看第一步 n = cap -1就明白了,这里是为了处理当cap本身即是2的指数时的情况。

因为计算机进行移位和位或操作十分迅速,所以,这个函数的执行效率其实很高。tablesizefor函数就是这样快速找到了一个大于等于cap的2的指数的值。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接

原文链接:https://blog.csdn.net/li_canhui/article/details/85088660

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部