关于JDK1.8 java HashMap的tableSizeFor的解析…
2020-04-22 16:06:25来源:博客园 阅读 ()
关于JDK1.8 java HashMap的tableSizeFor的解析:一个数最近2的幂次数方法
简介
一个数的最近2的幂次数,是java hashmap初始化方法指定容量里面对容量进行处理采用的方法
1.位运算符号介绍
符号 | 描述 | 运算规则 |
---|---|---|
& | 与 | 两个位都为1时,结果才为1 |
| | 或 | 两个位都为0时,结果才为0 |
^ | 异或 | 两个位相同为0,相异为1 |
~ | 取反 | 0变1,1变0 |
<< | 左移 | 各二进位全部左移若干位,高位丢弃,低位补0 |
>> | 右移 | 各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移) |
>>> | 无符号右移 | 在右移的基础上,高位补0,无论有符号数还是无符号数 |
<<< | 没有 |
2.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; }
测试
public static void main(String[] args) { hightwo(0); hightwo(7); hightwo(32); } private static void hightwo(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; System.out.println((n<0) ? 1 : (n+1)); }
结果:
解析:计算容量,通过参数中指定的容量,得到离2的n次幂最近的数返回(数大于等于原来输入cap)
思路:先将cap的低位全变1,之后再+1,使低位进位变0,高位变1
举例cap为7
cap:7 二进制 0000 0111
n cap-1 6 0000 0110
0000 0011 n>>>1
0000 0110 n
==================
0000 0111 n|n>>>1
0000 0001 n>>>2
0000 0111
==================
0000 0111 n|n>>>2 低位全为1,后续操作结果一样
...
n 0000 0111 7
cap = n+1 = 8
问题:关于为什么cap首先减1?
回答:防止本来就是2的次幂数返回2倍,比如cap是8,若不减1,则返回16而不是8了
举例
cap 8
0000 1000
0000 0100 n>>>1
===================
0000 1100 n|n>>>1
0000 0011 n>>>2
0000 1100
====================
0000 1111 n|n>>>2 低位全为1,后续操作结果一样
0000 0001 n+1
=====================
0001 0000 16
cap = 15 + 1 = 16
3.其它
一个数的最近2的幂次数(小于等于原数)
private static int lowtwo(int n) { n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; n -= n>>>1; return (n <= 0) ? 1 : n; }
思路:将cap低位变1,再无符号右移1位,cap再减之,将低位变0,高位保留
测试
public static void main(String[] args) { System.out.println(lowtwo(0)); System.out.println(lowtwo(7)); System.out.println(lowtwo(32)); } private static int lowtwo(int n) { n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; n -= n>>>1; return (n <= 0) ? 1 : n; }
/*结果*/
1
4
32
原文链接:https://www.cnblogs.com/fooleryang/p/12751204.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash