Java8–HashMap之tableSizeFor

首先

基本类型:int 二进制位数:32

包装类:java.lang.Integer

最小值:Integer.MIN_VALUE= -2147483648 (-2的31次方)

最大值:Integer.MAX_VALUE= 2147483647 (2的31次方-1)

java 8HashMap 构造函数

java 8 中在创建hashMap的时候有个构造函数如下:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

其中initialCapacity是初始容量,这个容量经过tableSizeFor加工后就变为了大于输入参数且最近的2的整数次幂的数,当然如果输入参数大于2 30 则会返回2 30 ,因为int最大是2 31 -1不是2的倍数,最大的2的次方就是2 30

tableSizeFor解析

java8源码如下:

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

详解如下:

先来分析有关n位操作部分:先来假设n的二进制为01xxx…xxx。接着

对n右移1位:001xx…xxx,再位或:011xx…xxx

对n右移2为:00011…xxx,再位或:01111…xxx

此时前面已经有四个1了,再右移4位且位或可得8个1

同理,有8个1,右移8位肯定会让后八位也为1。

综上可得,该算法让最高位的1后面的位全变为1。

最后再让结果n+1,即得到了2的整数次幂的值了。

由于int是32位,所以>>>16便能满足。

Java8--HashMap之tableSizeFor

而关于为啥要int n = cap – 1;

代码解释吧:

Java8--HashMap之tableSizeFor

输入如下:

如果不减去1得到的结果为16显然不对,输入8的时候不小于输入结果的最小2的次方应该是8。那么这里减一的意义就是避免这种情况。

参考文章

Java8—HashMap之tableSizeFor()

原文 

https://segmentfault.com/a/1190000021053887

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java8–HashMap之tableSizeFor

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址