Temporary nodes in ConcurrentHashMap Java 8

Question

Looking at java.util.ConcurrentHashMap.putVal(), I came across some conditions that checks if any object(node) in array has hashcode() as -ve value. This code, for eg:

    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED) // THIS HERE???
            tab = helpTransfer(tab, f);

note that it checks for fh==MOVED and MOVED is -1, so what objects(nodes) have negative hashcode() in CHM?

Further reading the documentation, it says there could be 3 types of nodes could be there(first in bin) apart from real nodes and their hashcode() could be among:

    static final int MOVED     = -1; // hash for forwarding nodes
    static final int TREEBIN   = -2; // hash for roots of trees
    static final int RESERVED  = -3; // hash for transient reservations

I can understand first is for tempory reference while resizing map but I can not seem to understand the usage of -2 and -3 hashcode() . Help?

Answer 1

TREEBIN is used to mark a TreeBin and RESERVED marks ReservationNode used in compute and computeIfAbsent methods. These hash code can be use to determine what is the type of a bin node.

There are 4 types of bin node, Node with hash >= 0, TreeBin with hash == TREEBIN, ForwardingNode with hash == MOVED, ReservationNode with hash == RESERVED.

These nodes with different hash code are used to avoid concurrent issue. Although we can use instanceof to distinguish them from each other, it's more effecient to distinguish Node from others because they are all subclass of Node. For taking acount of efficiency, this hash code design is useful.

Further more, there are other reason for creating these types. For example, compared with HashMap, we have no need to moveRootToFront(would cause problem when other thread is finding) after using TreeBin, because TreeBin stores the root of the tree.