Why the HashMap#resize implementation is so complex?

user_4428471 0
Viewed 325

After reading source code of java.util.HashMap#resize , I'm very confused with some part -- that is when some bin has more than one node.

else { // preserve order
    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;
    }
}

Why I feel this part is no need to exist? Just use below code

newTab[e.hash & (newCap - 1)] = e;

is ok -- I think they have the same effect.

So why bother to have so many code in the else branch?

hashmap java
2 Answers

At resize, every bin is split into two separate bins. So if the bin contained several linked items, you cannot move all of them into the single target bin based on the hash of the first item: you should recheck all the hashes and distribute them into "hi" and "lo" bin, depending on the new significant bit inside the hash ((e.hash & oldCap) == 0). This was somewhat simpler in Java 7 before the introduction of tree-bins, but the older algorithm could change the order of the items which is not acceptable now.

user_48562580
Related