ConcurrentHashMapの内部処理の中で、要素数を管理するaddCountメソッドは非常に重要な役割を果たします。本稿では、このメソッドがどのように動作するのか、コードを交えて詳しく解説します。このメソッドは主にputValメソッドから呼び出されます。

ソースコードの動作分析

private final void addCount(long x, int check) {
    CounterCell[] as; 
    long b, s;

    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;

        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }

        if (check <= 1)
            return;

        s = sumCount();
    }

    if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;

        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

CounterCell配列の役割

ConcurrentHashMapでは、要素数のカウントにCounterCell配列を採用しています。通常のコレクションであれば、単一のsize変数で管理するのが一般的ですが、マルチスレッド環境ではその変数へのアクセス競合が激しくなり、パフォーマンスが低下する可能性があります。そこでConcurrentHashMapは、カウントを複数のセルに分散させることで、競合を緩和しています。

public class ConcurrentHashMap<K,V> extends Abstract{
    // セル配列の初期化・拡張中を示すCASフラグ
    private transient volatile int cellsBusy;
    // 要素数を分散して保持するセル配列
    private transient volatile CounterCell[] counterCells;

    @sun.misc.Contended 
    static final class CounterCell {
        volatile long value;
        CounterCell(long x) { value = x; }
    }

    // 全セルの値を合計して要素数を取得
    final long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }
}

上記の通り、CounterCell配列の各要素が個別にカウントを保持し、size()メソッドではそれらを合算することで全体の要素数を算出します。

addCountメソッドの処理概要

addCountメソッドは主に以下の2つの処理を行います。

• テーブルの要素数を1増加させる：baseCountのCAS更新を試み、失敗した場合はCounterCellを使用して分散更新を行います。
• リサイズの必要性を確認し、必要な場合は自らリサイズを開始するか、進行中のリサイズに参加する。

注目すべき点は、リサイズ開始時にsizeCtlの下位16ビットが2増加する点です。これは、リサイズが完了した際にsizeCtlがrs + 1になることを意味し、sc == rs + 1はリサイズ終了の合図となります。また、リサイズに参加できるスレッド数の上限が65535であるのも、下位16ビットの表現範囲に起因します。