Java基础->HashMap之为什么数组长度是2的n次方

（1）hashcode跟2的n次方减一做与运算；
减一为了保证取值范围，与运算可以减少碰撞以及值完全取决于hashcode
这跟生成数组index有关，常规做法是求余（int index=hash%length），使得index在[0,length-1]这个区间，而HashMap的做法是与运算（int index=hash^length-1）；
以length=16（2的4次方）为例；

    public void test() {
        int length = 16;//16为2的4次方，二进制为0001 0000，而length - 1=15，二进制就是0000 1111；
        int hashCode = 16;//假设hashCode为16，二进制为是0001 0000
        //hashCode^length - 1=0，0000 1111^0001 0000，结果是0，元素存放的下标就是0，这跟hashCode%length（16%16）结果一致
    }

length减一目的：使得原来1右边低位都为1、左边高位都为0，那么无论多大的hashCode做与运算，结果都在[0,length-1]之间
不采用求余运算，是因为位运算比较快。

Tips：与运算，两个都是1，结果是1，而且与运算有点截取的意思，只截取低几位作为结果，高位不管；或运算，其中一个是1，结果是1，异或运算，两个相同，结果是0，不同为1；

Tips：采用类似求余的方式，是因为这样得到的结果比较均匀（数学上统计的、不是我说的）；

Tips：计算得到的index完全取决于hashCode的后几位，增加了随机性；

Tips：如果长度是10，那么length=9=1001，与上1111、1001、1011、1101，结果都是1001，就容易产生冲突；

让一组数分布到某个范围，一般采用求余，也就是与运算，数值与上length-1，这样保证它在一个范围呢，所以也就决定了是2的n次方。如果不是2的n次方，例如10，length=9=1001，采用与运算会产出多个冲突，用或运算，可能会溢出，因为或增加可出现1的可能性，例如1001或上1110；