Why the HashMap#resize implementation is so complex?

Question

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?

Thanks! but maybe you misunderstood me, I'm not confused of `e.hash & (newCap - 1)`. I'm confused of why in the else branch need so many code I think just use `newTab[e.hash & (newCap - 1)] = e;` could have the same effect. — zhuguowei, May 26 '17 at 13:57
see related question: https://stackoverflow.com/questions/45404580/hashmap-resize-method-implementation-detail — Eugene, Jul 30 '17 at 20:53

score 2 · Answer 1 · answered Oct 03 '19 at 06:36

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.

score 0 · Answer 2 · edited May 27 '17 at 01:07

EDIT: The threshold for treefying a bin changes as the table is made bigger. That's what it is doing.

I haven't read the entire file, but this could be a possible reason (line 220)

The use and transitions among plain vs tree modes is complicated by the existence of subclass LinkedHashMap. See below for hook methods defined to be invoked upon insertion, removal and access that allow LinkedHashMap internals to otherwise remain independent of these mechanics. (This also requires that a map instance be passed to some utility methods that may create new nodes.)

Why the HashMap#resize implementation is so complex?

2 Answers2