为什么HashMap的底层数组长度为何总是2的n次方？

1 说明

每次扩容后，原数据都会进行数据迁移，根据二进制的计算，扩容后数据要么在原来位置，要么在【原来位置+扩容长度】，这样就不需要重新hash，效率上更高。

HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂。

使数据分布均匀，减少碰撞
当length为2的n次方时，h&(length - 1) 就相当于对length取模，而且在速度、效率上比直接取模要快得多

（1）当length为2的N次方的时候，h & (length-1) = h % length

为什么&效率更高呢？因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高

（2）当length为2的N次方的时候，数据分布均匀，减少冲突

此时我们基于第一个原因进行分析，此时hash策略为h & (length-1)。

2 当length为2的N次方的时候，h & (length-1) = h % length

为什么&效率更高呢？因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高

案例1-a: &的位置在前，%的位置在后的测试

源码：

public static void main(String[] args) {
        long time = System.currentTimeMillis();
        int size = 1 << 30;
        int[] datas=new int[size];
        System.out.println(size);
        for (int i = 0; i < size; i++) {
            int b = i & (size - 1);
            datas[i]=b;
        }
        System.out.println(System.currentTimeMillis() - time);
        time = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            int b = i % size;
            datas[i]=b;
        }
        System.out.println(System.currentTimeMillis() - time);
    }

执行结果：

1
2
3

1073741824
2504
3276

案例1-b：&的位置在前，&的位置在后的测试

源码：

public static void main(String[] args) {
    long time = System.currentTimeMillis();
    int size = 1 << 30;
    int[] datas=new int[size];
    System.out.println(size);
    for (int i = 0; i < size; i++) {
        int b = i % size;
        datas[i]=b;
    }
    System.out.println(System.currentTimeMillis() - time);
    time = System.currentTimeMillis();
    for (int i = 0; i < size; i++) {
        int b = i & (size - 1);
        datas[i]=b;
    }
    System.out.println(System.currentTimeMillis() - time);
}

执行结果：

1
2
3

1073741824
5026
552

通过上面两个案例虽然有时间差，这里有JIT的即时编译影响，但是时间任然可以看出&的效率比%的快。

3 当length为2的N次方的时候，数据分布均匀，减少冲突

当length=15为奇数情况：

h	h&(length-1)	result
0	0000&1110	0
1	0001&1110	0
2	0010&1110	2
3	0011&1110	2
4	0100&1110	4
5	0101&1110	4
6	0110&1110	6
7	0111&1110	6
8	1000&1110	8
9	1001&1110	8
10	1010&1110	10
11	1011&1110	10
12	1100&1110	12
13	1101&1110	12
14	1110&1110	14
15	1111&1110	14

当length=16为偶数情况：

h	h&(length-1)	result
0	0000&1111	0
1	0001&1111	1
2	0010&1111	2
3	0011&1111	3
4	0100&1111	4
5	0101&1111	5
6	0110&1111	6
7	0111&1111	7
8	1000&1111	8
9	1001&1111	9
10	1010&1111	10
11	1011&1111	11
12	1100&1111	12
13	1101&1111	13
14	1110&1111	14
15	1111&1111	15

通过上面可以当 length 为15时总共发生了8次碰撞，同时发现空间浪费非常大，因为在 1、3、5、7、9、11、13、15 这八处没有存放数据。 length为16偶数的情况下分布更加均匀。这里其实更应该说是length-1 如果为1111、11111、111111、1111111这样的情况才能让数据分布的更加均匀减少碰撞。