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）比较
参考：
