HashMap中 工具方法tableSizeFor的作用
【转】 https://blog.csdn.net/fan2012huan/article/details/51097331
首先看下该方法的定义以及被使用的地方
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;
}
public HashMap(int initialCapacity, float loadFactor) {
// code...
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor()这个方法的作用是找到大于等于给定容量的最小2的次幂值
>>>这个符号在java里是无符号右移的意思。
接下来分析一下这个方法的作用。
第一句
int n = cap - 1;
先不用考虑,我们分析完后面的之后再回过头来看它
然后是第二句
n |= n >>> 1;
我们这里假设n的初始值为9,那么9的二进制表示是
00000000 00000000 00000000 00001001
那么经历一次右移之后,二进制表示是
00000000 00000000 00000000 00000100
这两个值进行异或之后,就是
00000000 00000000 00000000 00001100
这里我们如果看最高的1的话,那么可以发现右移1位并且异或之后,使得最高位的右边一位也是1.
同理,我们可以下一句右移2位并且异或之后,使得最高两位1的后两位也是1.
我们之后运行到最后一个右移,可以发现n的值变为了
00000000 00000000 00000000 00001111
当然该值大于1并且小于最大值那么+1之后,该值就变成了
00000000 00000000 00000000 00010000
惊讶的发现这个值不就是2的次幂嘛!!!
此时我们回到第一句-1,如果给定的n已经是2的次幂,但是不进行-1操作的话,那么得到的值就是大于给定值的最小2的次幂值。
至于为什么右移到16位,可以得到的最大值是32个1
11111111 11111111 11111111 11111111
这个是因为java的int类型用4个字节32位来进行存储的。最往后没有意义。
最新文章
- C#重写一个控件Label
- React-native之Alert
- mysql的卸载方法
- cookie 、session、JSESSIONID
- android studio添加三方jar包
- 创建第一个MVC
- 强大的grep命令
- RxJava开发精要1-从.NET到RxJava
- php中foreach()函数与Array数组经典案例讲解
- JAVA $ JSP
- web api 上传
- 关于SpringMVC中找不到<;mvc:resources/>;标签的解决办法
- Windows 7 USB DVD Download Tool 制作的U盘无法启动安装Windows7 SP1
- mysql 安装部署
- 【kafka】生产者速度测试
- 1 创建一个存储过程,以及对存储过程的调用 MySQL
- Codeforces Round #371 (Div. 2) C. Sonya and Queries 水题
- Android Volley 库的使用
- Codeforces777D Cloud of Hashtags 2017-05-04 18:06 67人阅读 评论(0) 收藏
- P4291 [HAOI2008]排名系统