满嘴都是糖果

HashMap的容量总是2的幂次

秘密在哪呢？

提高模运算性能

如何把hashmap中元素的位置尽量分布的均匀一些，减少碰撞时去链表中寻找的次数。因此使用模运算的方式，对hashcode取膜来找到对应的位置，但是模运算的消耗较大，因此找到一种更快的方式取代膜运算

index = (n - 1) & (hash = hash(key)) //hashcode & (length-1) == hashcode % length

resize()时无需重新计算元素hash值

在扩容的时候，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这是一个非常消耗性能的操作。由于n变为两倍，不需要重新计算hash，原先在oldTab[i]位置的元素在resize后要么在newTab[i]，要么在newTab[i+oldCap],而且只有oldTab[i]上的元素会被分配到这两个位置，根据当前元素的hash与oldcap的&值是否等于0即(e.hash & oldCap) == 0，然后直接赋值newTab[i]=low, newTab[i+oldCap]=high

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);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

hash1放入 newTab[i+oldCap]，hash2放入newTab[i]

This site is open source. Improve this page.