HashMap的tableSizeFor方法：求一个数的最小的2^n

来源：HashMap的tableSizeFor方法代码

private static 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 >= 1 << 30 ? 1 << 30 : n + 1);
    }
复制代码

• 为什么要使用 cap – 1做位运算？

  如果用 cap 做位运算，当 cap 为2 ⁿ 时，会变成2 ⁿ⁺¹ ，而使用 cap – 1 就巧妙地避免了这种情况

• 为什么要与1，2，4，8，16做位运算

  目的：将最高位后面的所有数都设置为1（只需要关注红色数字部分，因为红色数字部分才是每次位运算变化的地方，而黑色数字部分对最终的结果是没有任何影响的）

  • 非2 ⁿ 数：

  
  

  • 2 ⁿ 数：

  
  

• 最大值为什么选择 1 << 30，而不是Integer.MAX_VALUE

  因为 Integer的最大值为 1 << 31 – 1（2147483647），是一个奇数，不是2的n次幂， 而 1 << 31 是一个负数（-2147483648），所以最大值只能是 1 << 30（1073741824）