HashMap中tableSizeFor方法解析

【饿了么、美团】外卖红包领取地址 >> 能省一点是一点

HashMap中有一个计算大于等于cap且结果为2的N次方整数的方法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;
}

先分析一下2的N次方整数的二进制有什么特点?
1、二进制表示下,只有一位是1,其他的都是0。
2、假设需要计算的数为n,结果又可以表示为,n的最高位1开始往右(地位),全部变成1之后的值,再加上1。

举个例子,假设n为10,则n的2进制为:

0000 1010

从最高位1开始往右全变1得:

0000 1111

再加1得:

0001 0000

十进制结果为16,也就是结果值。

其中代码中的n |= n >>> 1;这几行做的事就是为了变1,具体怎么变往后再说,先看一下为啥n要等于cap-1。
假设给定的cap已经是2的N次方了,这个时候如果不-1,按照逻辑变1之后再加1,结果就会变成2倍的cap了,也就与应有的结果不一致,也就是因为要处理这种特殊情况,所以需要先执行n=cap-1的操作。

n |= n >>> 1;这几行,这几行是变1的核心。
原理是,将n的值右移1位,这个时候比1低一位的值也变成了1,然后进行一下或运算,即可得到2位1。
这个时候因为已经可以保证高位前2位是1了,所以可以继续右移2位继续进行或运算,可以得到4位1。
依葫芦画瓢,高位前4位是1,继续右移或运算,直到n |= n >>> 16;结束。(因为int是32位的,所以执行到16即可)
说起来比较抽象,拿n=8举例就可以比较清楚的看懂原理。

n=8;            //0000 1000
n |= n >>> 1;   //0000 1000 | 0000 0100 = 0000 1100
n |= n >>> 4;   //0000 1100 | 0000 0011 = 0000 1111
n |= n >>> 8;   //0000 1111 | 0000 0000 = 0000 1111
n |= n >>> 16;  //0000 1111 | 0000 0000 = 0000 1111

因为在计算机系统中,位运算非常的快,所以通过这个方法的算法即可快速的得到想要的值,还是挺巧妙的,学习了一波。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

先科(SAST) 微信语音收款播报器wifi音响 二维码收钱码手机无线蓝牙音箱扩音器 蓝牙版收款提示器
¥45.90
【发4盒共40包】人参五宝茶男士男人玛咖黄精肾八宝补茶叶养生花茶包熬夜泡水喝的饮品红枣枸杞搭气血 人参黄精枸杞五宝茶 4盒装
¥36.00
临犀书法字帖现代汉语常用7000字庹纯双回米格楷书高频常用字高考考研公务员考试通用卷面整洁规范好字
¥19.40
爱康尼 kn95口罩儿童尺寸自营一次性口罩独立包装秋冬学生款3-10岁摘星兔
¥38.60
都市牧场 干吃牛奶片高钙牛初乳儿童零食特浓牛奶片送礼糖果办公室休闲零食 原味52.8g
¥10.90
贝拉豆入户地垫门垫进门家用脚垫门口玄关垫子地毯D76脚垫60*90cm
¥26.80
科德宝(micronAir)空气滤清器空气滤芯空气格AF676适用于(凯美瑞/雷凌/雷克萨斯RX200tRX300RX450h)
¥35.00
品胜 数据线三合一充电线伸缩 苹果安卓Type-c快充 适用iPhone14/13/12小米华为手机车载一拖三便携收纳多头
¥38.00