工作中你发现哪些细节惊艳到你了--HashMap之tableSizeFor

原创
2021/09/09 12:08
阅读数 124

今天在使用HashMap的时候,突然想到如果我指定了map的初始容积,但是如果值是0或1 的时候hashMap到底做了什么(如果不指定是16) 构造方法如下:

   public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

然后我就看到了下面的这段代码,初看这都是你什么,仔细看下原来是针对二进制的计算,那么这个方法到底做了什么呢?

    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 操作呢 这个放在最后分析 加入我们的入参是5 减1 后是 4 对应的二进制是多少呢 0000 0000 0000 0100; n |= n >>> 1; 可以写成0000 0000 0000 0100 |=0000 0000 0000 0010 >>结果 0000 0000 0000 0110 转换成十进制的结果是 6 ;

n |= n >>> 2; 可以写成0000 0000 0000 0110 |= 0000 0000 0000 0011 >> 结果 0000 0000 0000 0111 转换成十进制的结果是 7;

n |= n >>> 4; 可以写成0000 0000 0000 0111 |= 0000 0000 0000 0000 >> 结果 0000 0000 0000 0111 转换成十进制的结果是 7;到这里 结果已经不会发生变化了 我们继续代码逻辑

n |= n >>> 16; 可以写成0000 0000 0000 0111 |= 0000 0000 0000 0000 >> 结果 0000 0000 0000 0111 转换成十进制的结果依然是 7;

最后return 语句中 判断了当前n的值 经过逻辑计算 对n值进行了加1 的操作 所以最终结果是8 也就是2的3次方.

那么如果最开始的时候不进行 cap-1 n最后的结果是7 可能数字太小不足以影响结果 那么我们把测试环境换成16 正常情况下 结果也是16 但是如果不减1 结果就变成32了 这样的做法应该可以避免在入参已经符合条件的时候 结果增加一倍的情况

验证猜想 入参16的情况 0000 0000 0001 0000 |= 0000 0000 0000 1000 >>0000 0000 0001 1000 最终结果0000 0000 0001 1111 ->32 如果 减1 15的的情况 0000 0000 0000 1111|= 0000 0000 0000 0111 >>0000 0000 0000 1111 最终结果0000 0000 0000 1111 ->16 看来猜想是对的 就是针对符合条件的结果 进行最高位减1 可以避免结果翻倍的情况

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部