HashMap下标计算详解

HashMap 计算方法为：(n - 1) & hash 具体见putVal
解读：由于n-1高位全部为0 因此(n - 1) & hash只会得到一个小于等于n-1的值，即在桶长度取值范围内.
为何不用取余运算，写一段模拟程序，我们来对比下速度：

        Random random = new Random();
        int[] array =new int[8];
        int[] array2 =new int[8];
        long start = System.currentTimeMillis();
        int [] randNum = new int[1000000000];
        for (int i = 0; i < 1000000000; i++) {
            randNum[i] = random.nextInt(Integer.MAX_VALUE);
        }
        System.out.println("随机数生成s耗时"+(System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        for (int i = 0; i < 1000000000; i++) {
            int temp = randNum[i];
            int temp1 = temp & 7;
            array[temp1] ++;
        }
        System.out.println("&运算耗时"+(System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        for (int i = 0; i < 1000000000; i++) {
            int temp = randNum[i];;
            int temp2 = temp % 8;
            array2[temp2] ++;
        }
        System.out.println("%运算耗时"+(System.currentTimeMillis() - start));
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(array2));

运行结果：

随机数生成s耗时16047
&运算耗时842
%运算耗时1135
[125000039, 125000018, 125000011, 125000048, 124999883, 125000270, 124999981, 124999750]
[125000039, 125000018, 125000011, 125000048, 124999883, 125000270, 124999981, 124999750]

我们把数字改成5

随机数生成s耗时15465
&运算耗时1085
%运算耗时1738
[499999525, 0, 0, 0, 500000475]
[200012563, 199986986, 199985673, 199981177, 200033601]

结论：

&位运算速度快于%，缺点：某些奇数如5 时分布不均匀。
联系下另一个方法：tableSizeFor 会将我们传入容量返回为2的倍数。经过实际测试 16 ，32 &位运算比较均匀。