关于JDK1.8 java HashMap的tableSizeFor的解析…

2020-04-22 16:06:25来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

关于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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:MyEclipse/Eclipse结构的JavaWeb项目导入Eclipse中运行教程 步骤

下一篇:SpringBoot系列(九)单,多文件上传的正确姿势