CODEWITHSUNDEEP
javamultithreadingconcurrenthashmap
JerryLin
JerryLin

Reputation: 129

A confusion about the source code for ConcurrentHashMap's putVal method

Here is part of codes for putVal method:

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();  // lazy Initialization
        //step1,tabAt(...) is CAS
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //step2,casTabAt(...) is CAS
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
       ...
    return null;
}

Suppose there are currently two threads, A and B, and when A executes the step1 , it gets true ,but at the same time B also executes step1 and gets true as well. And both A and B execute step2.

enter image description here

from this situation, B's Node replace the A's Node, or said A's data is replaced by B, this's is wrong.

I don't know is it right or wrong, can anyone help me to solve it?

Upvotes: 1

Views: 155

Answers (1)

nyarian
nyarian

Reputation: 4375

Here's how casTabAt is implemented:

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

Whereas U is declared as follows: private static final sun.misc.Unsafe U;. Methods of this class guarantees atomicity at low level. And from this usage:

casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))

we can see, assuming that the third parameter of compareAndSwapObject is expected value, that, due to atomicity guaranteed, either A or B thread that executes compareAndSwapObject first will see null here and compareAndSwapObject will actually replace the object, whereas the next thread executing compareAndSwapObject won't change the value, because the actual value is not null anymore, whereas null was expected as a condition to make a change for a value.

Upvotes: 2

Related Questions