ArrayList の問題点

まずは ArrayList を取り上げます。ArrayList は 다음과 같이宣言できますが、複数のスレッドから同時にアクセスすると問題が発生します。

ArrayList<String> dataList = new ArrayList<>();

ArrayList の内部構造について解説します。JDK 7 以前では、初期容量が 10 の Object 型配列が使用されていました。JDK 8 以降では、インスタンス生成時には空の配列となり、初回追加時に容量 10 となる遅延初期化方式が採用されています。容量拡張は現行の 1.5 倍ずつ行われ、Arrays.copyOf() メソッドが利用されます。たとえば、容量 10 から 15、15 から 22 へと増加していきます。

それでは本題に入り、マルチスレッド環境での動作を確認してみましょう。

ExecutorService executor = Executors.newFixedThreadPool(10);
for (int i = 0; i < 30; i++) {
    final int index = i;
    executor.submit(() -> {
        dataList.add(UUID.randomUUID().toString().substring(0, 8));
        System.out.println(dataList);
    });
}
executor.shutdown();

このコードを実行すると、以下の例外が発生します。

java.util.ConcurrentModificationException

この例外は、複数のスレッドが同一の ArrayList インスタンスに対して同時に読み書きを行い、競合が発生したことが原因です。スレッド間の同期机制がないため、データの整合性が失われます。

解決策として、以下の3つのアプローチがあります。

解決策1：Vector の利用

ArrayList<String> dataList = new Vector<>();

Vector は、add メソッドに synchronized キーワードが付与されており、排他ロックを獲得したスレッドのみが操作できます。そのため、スレッドセーフですが、同期処理のオーバーヘッドによりパフォーマンスが低下します。这就是为什么 Vector は安全ですが効率が悪いと言われる所以です。

解決策2：Collections.synchronizedList() の利用

ArrayList<String> dataList = new ArrayList<>();
ArrayList<String> synchronizedList = Collections.synchronizedList(dataList);

Collections クラスの static メソッドである synchronizedList() を使用することで、任意の ArrayList をスレッドセーフなリストに変換できます。

解決策3：CopyOnWriteArrayList の利用

CopyOnWriteArrayList<String> dataList = new CopyOnWriteArrayList<>();

JDK 1.5 で導入された java.util.concurrent パッケージに属するクラスです。

public class CopyOnWriteArrayList<E>
extends Object
implements List<E>, RandomAccess, Cloneable, Serializable

CopyOnWriteArrayList は、volatile修飾された Object[] 配列を内部に保持しています。add() メソッドでは、ReentrantLock を使用した排他制御が行われます。書き込み操作に際しては、元の配列のコピーを作成し、新しく拡張した配列に要素を追加後、参照を更新する「コピーオンライト」パターンが採用されています。

public boolean add(E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] currentArray = getArray();
        int currentLength = currentArray.length;
        Object[] newArray = Arrays.copyOf(currentArray, currentLength + 1);
        newArray[currentLength] = element;
        setArray(newArray);
        return true;
    } finally {
        lock.unlock();
    }
}

Capacity の拡張には Arrays.copyOf() が使用されますが、1要素ずつしか増加しません。

HashSet の問題点

続いて Set インタフェースの実装クラスである HashSet について説明します。

HashSet の内部構造は HashMap であり HashMap に依存しています。 HashSet のコンストラクタを覗くと、内部で new HashMap() が呼び出されていることがわかります。

Map への要素追加は Key-Value ペアで行われますが、HashSet は重複を許容しないコレクションです。この矛盾を解決するのが HashSet の実装メカニズムです。add() メソッドは内部で HashMap の put() メソッドを呼び出し、Set に追加する要素を key として使用します。Value には特に意味のないダミー値（定数）が設定されます。

HashSet<String> uniqueSet = new HashSet<>();
ExecutorService executor = Executors.newFixedThreadPool(10);
for (int i = 0; i < 30; i++) {
    final int index = i;
    executor.submit(() -> {
        uniqueSet.add(UUID.randomUUID().toString().substring(0, 8));
        System.out.println(uniqueSet);
    });
}
executor.shutdown();

ArrayList と同様に ConcurrentModificationException が発生します。

解決策として、以下の2つのアプローチがあります。

解決策1：Collections.synchronizedSet() の利用

HashSet<String> uniqueSet = new HashSet<>();
Set<String> safeSet = Collections.synchronizedSet(uniqueSet);

Collections クラスの synchronizedSet() メソッドを使用して、既存の HashSet をスレッドセーフな Set に変換できます。

解決策2：CopyOnWriteArraySet の利用

CopyOnWriteArraySet<String> uniqueSet = new CopyOnWriteArraySet<>();

CopyOnWriteArraySet も java.util.concurrent パッケージに含まれるクラスです。

public class CopyOnWriteArraySet<E>
extends AbstractSet<E>
implements Serializable

内部的には CopyOnWriteArrayList を活用しており、同様のコピーオンライト方式でスレッドセーフを実現しています。

HashMap の問題点

最後は Map インタフェースの実装クラスである HashMap についてです。

HashMap は 順序保証のない Key-Value ストア であり、内部構造は配列＋ singly linked list（単方向リスト）＋ Red-Black Tree（赤黒木）で構成されています。

Map には Node インスタンスが格納され、各 Node には Key と Value のペアが保持されています。初期容量は 16、ロードファクタは 0.75 です。容量が threshold（初期値では 16 × 0.75 = 12）に達するとリハッシュ処理が実行され、容量は元の2倍に拡張されます。これらのパラメータはコンストラクタでカスタマイズ可能です。

Constructor and Description
HashMap()
デフォルトの初期容量（16）とデフォルトのロードファクタ（0.75）で空の Map を作成します。
HashMap(int initialCapacity)
指定された初期容量とデフォルトのロードファクタ（0.75）で空の Map を作成します。
HashMap(int initialCapacity, float loadFactor)
指定された初期容量とロードファクタで空の Map を作成します。
HashMap(Map<? extends K,? extends V> map)
指定された Map と同じマッピングを持つ新しい Map を作成します。

HashMap のマルチスレッド環境での動作を確認します。

ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();
ExecutorService executor = Executors.newFixedThreadPool(10);
for (int i = 0; i < 30; i++) {
    final int index = i;
    executor.submit(() -> {
        String threadKey = "Thread-" + index;
        String randomValue = UUID.randomUUID().toString().substring(0, 8);
        concurrentMap.put(threadKey, randomValue);
        System.out.println(concurrentMap);
    });
}
executor.shutdown();

HashMap を 그대로使用すると、ArrayList や HashSet と同様に ConcurrentModificationException が発生します。

解決策として、ConcurrentHashMap を使用します。

HashMap<String, String> map = new ConcurrentHashMap<>();

java.util.concurrent パッケージに属する ConcurrentHashMap は、高性能な並行処理を実現するために設計されています。

public class ConcurrentHashMap<K,V>
extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable

ConcurrentHashMap は、Java 7 まではセグメントロック方式、Java 8 以降は CAS（Compare-And-Swap）操作と synchronized を組み合わせた細粒度のロック機構を採用しています。これにより、複数のスレッドが Map の異なる領域を同時に操作でき、高い并发性が実現されます。

以上が、Java の並行処理環境においてスレッドセーフでないコレクション（ArrayList、HashSet、HashMap）とその解決策についての解説でした。