Java ConcurrentHashMap initialization

Viewed 208

I am currently reading through the source code of ConcurrentHashMap in jdk1.8, and I find that initalTable() method a bit confusing.

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
//some fields revolved in this method
transient volatile Node<K,V>[] table;
private transient volatile int sizeCtl;

  private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];//place 1
                        table = tab = nt;//place 2
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }
}

So main confusion mainly focused on the following points:

  1. Why would we need while((tab = table) == null || tab.length == 0) to check both table is not null and its length is not 0 and determine whether to continue the loop, so it exits only when both two condition is false. I just cannot think of a situation when the table is not null but with a length of 0, since it is initialized in the else if block where n is always given a value larger than 0. Then why we need the both rather than only one?

2. The second question is not a problem but rather I just want to check whether my assumption makes sense. So imagine two threads run subsequently but in a very close manner. The later thread can enter the else if block if the earlier one hasn't reach the point of initialization of table or place 2 nor has sizeCtl been updated, then the second thread will be able to enter the else if block, so table field will be initialized once more? Will this scenario happens in rare situation? I know this will not affect the correctness of the program but will it happens in some situation?

Hope anyone can give me a clarification. Thanks in advance.


Updated: I forgot the fact that one successful CAS operation will swap the sizeCtl to -1 which will block other threads from entering the else if block, but I am still not clear about why we need two conditions in the if and while.

1 Answers

It is not sufficient to analyze the method initTable in isolation. You need to take into account other methods which can also modify table and sizeCtl fields. There you will notice that e.g. transfer decreases sizeCtl by one using CAS. I'm not sure if this can lead to table.length == 0 at any point in time, but note that this whole process is much more complicated and that initTable can be called concurrently with resize operation.

Related