static final int tableSizeFor(int cap) {
// cap 是初始容量
// 返回值作为下一次 resize 的阈值
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// 这个运算的目的得到一个最接近 cap 的 2 的幂次方作为阈值
// MAXIMUM_CAPACITY 等于 1 << 30
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
核心思想
第一个大于或等于 cap 的 2 的幂次方数为,将二进制的 cap 的第一个 1 之后的所有 bit 置为 1 之后加 1。
分析
先不考虑 n = cap - 1
的作用,假如 n 不等于 0,那么二进制的 n 至少有一个 bit 为 1,那么从第一个 1 开始,经过第一次 n |= n >>> 1
之后,n 的开头(忽略第一个 1 前面的 0 )有了两个 1,接着 n |= n >>> 2
使两个 1 右移之后异或变成四个 1,执行到最后,就可以将第一个 1 后面所有的 bit 都置为 1。加 1 之后得到的就是 2 的幂次方。
如果不进行 cap - 1
,那么假如一开始的 cap 就是 2 的幂次方的话,得到的结果将是 cap * 2。另外考虑 cap 为 0 的情况,如果不减 1,那么 n 里面就没有 1,这样就无法实现置 1 的操作,导致返回结果 为 1,不是 2 的幂次方。
总结
-
cap - 1
为了使最后的结果是大于或等于 cap 的 2 的幂次方,并且确保 n 的 bit 不全为 0 -
|= n >>>
实现了类似于复制的功能,先复制 1 个 1 得到 2 个 1,再复制两个 1 得到 4 个 1 -
n + 1
将一个尾部为 1 的整数转为 2 的幂次方
其他
-
为什么
MAXIMUM_CAPACITY = 1 << 30
因为这是 int 范围最大的 2 的幂次方数。
-
如果不使用这种方式应该如何寻找第一个大于或等于 cap 的数
- 暴力:将 cap 与每一个 2 的幂次方数(1 到 30)比较
参考:
网友评论