为什么 HashMap 长度必须是 2 的 n 次幂

2 的 n 次幂

1后面n个0

如：

2^3 = 1000

2^6 = 1000000

取索引的算法

取索引的算法是对hash值取模：hash%length，而直接取模%性能比位运算差，所以借助2的n次幂减去1并做与运算，就等价于取模：hash&(length-1)

JDK1.8 后扩容

JDK1.8后的扩容也是有一定技巧，直接和原先长度进行与运算，如果为0，还是在当前所以位置，如果不等于0（等于1），索引就等于当前索引加上原先数组长度的位置。

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

减少哈希碰撞

哈希碰撞就是不同的对象算出来的哈希值一样了，让数组均匀分配。