[Java] 同期化コレクションと並行コレクション

同期化されたコレクション

同期化されたコレクションは、主に以下のクラスがあります。

Vector
Hashtable
Collections.synchronizedXXX

これらのクラスはすべて、publicに宣言されたメソッドにsynchronizedキーワードを使用することで、内部の値を 1つのスレッドだけが使用できるように制御し、同時性を保証しています。

Vector

```javascript public class Vector extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { ... public synchronized boolean add(E e) { modCount++; add(e, elementData, elementCount); return true; } ... }

Vectorクラスの要素を追加するadd()メソッドを見てみると、synchronizedキーワードが見られます。つまり、内部的にVectorで要素の挿入操作が行われるときに、同期が保証されます。

Hashtable

```javascript public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); }

}

Hashtableクラスで同じvalueが存在するかどうかを確認するcontains()メソッドを見てみると、Vectorクラスと同様にsynchronizedキーワードが使用されていることが確認できます。

Collections.synchronizedXXX

Collections.synchronizedList()メソッドを使用して作成されるSynchronizedListクラスを見てみましょう。

```javascript static class SynchronizedList extends SynchronizedCollection implements List {

}

SynchronizedListクラスのメソッドを見てみると、すべてsynchronizedキーワードが使用されていることがわかります。ただし、 synchronizedブロックを使用して、mutexを介して同期を実装しています。すべてのメソッドはmutexオブジェクトを共有しているため、 1つのスレッドがsynchronizedブロックに入った瞬間、他のメソッドのsynchronizedブロックがすべてロックされます。

同期化されたコレクションの問題点

マルチスレッド環境で同期化されたコレクションを使用しなければならない場合もありますが、できる限り別の同期方法を使用することをお勧めします。理由は大きく2つあります。

複数の操作をまとめて単一の操作として使用する場合

同期化されたコレクションクラスは、マルチスレッド環境で同時性を保証します。しかし、複数の操作をまとめて1つの単一操作として活用する必要がある場合、問題が発生します。このような同期化されたコレクションを使用しても、正しく動作しない場合があります。

```javascript final List list = Collections.synchronizedList(new ArrayList()); final int nThreads = 2; ExecutorService es = Executors.newFixedThreadPool(nThreads);

for (int i = 0; i < nThreads; i++) { es.execute(new Runnable() {

}

上記のコードを実行すると、Thread Aがremove(0)を実行した瞬間にThread Bがclear()を実行すると、エラーが発生します。そのため、以下のように同期ブロックで囲む必要があります。

```javascript synchronized (list) { list.clear(); list.add("888"); list.remove(0); }

パフォーマンスの低下

共有オブジェクトを使用しようとするすべてのメソッドをsynchronizedメソッドにしたり、メソッド内部に同じ synchronizedブロックを定義すると、1つのスレッドがロックを取得した瞬間、他のスレッドはすべての同期メソッドを使用できなくなり、ブロッキング状態になります。このような繰り返しの現象は、パフォーマンスの低下につながる可能性があります。

並行コレクション

java.util.concurrentパッケージで提供されている並行コレクションの種類は次のとおりです。このうち、今回は一部だけを扱います。

CopyOnWriteArrayList
- Listクラスのサブクラスであり、オブジェクトリストを反復処理して検索する操作のパフォーマンスを最優先とした並行コレクションです。
ConcurrentMap
- 並行コレクションであり、インターフェースを見ると、追加しようとするアイテムが既存にない場合にのみ、新しく追加する put-if-absent、replace、conditional removeなどの操作が定義されています。
ConcurrentHashMap
- ConcurrentMapのサブクラスであり、HashMapを置き換えて並列性を確保した並行コレクションです。
ConcurrentLinkedQueue
- FIFO方式のQueueであり、並列性を確保した並行コレクションです。キューから取り出す要素がない場合は、すぐにリターンし、他の作業を実行します。
LinkedBlockingQueue
- ConcurrentLinkedQueueに似ています。ただし、キューが空の場合、キューからアイテムを取り出す操作は、新しいアイテムが追加されるまで待機し、逆にキューにサイズが指定されている場合、キューが指定されたサイズまでいっぱいになっている場合、キューに新しいアイテムを追加する操作は、キューに空のスペースが空くまで待機するという違いがあります。
ConcurrentSkipListMap、ConcurrentSkipListSet
- それぞれSortedMapとSortedSetクラスの並列性を高めるために進化した形です。

従来使用していた同期化されたコレクションクラスを並行コレクションに置き換えるだけで、特別なリスク要因なく、全体的なパフォーマンスを大幅に向上させることができます。

並行コレクションと対照的な同期化されたコレクションを比較しながら、詳しく見ていきましょう。

CopyOnWriteArrayList

同期化されたArrayListを作成する方法は、以下の2つがあります。

Collections.synchronizedList()
CopyOnWriteArrayList

Collections.synchronizedList()は、JDK 1.2バージョンで追加されました。このコレクションは、すべての読み取りと書き込み操作に対して同期化されているため、柔軟性に欠ける設計と言えるでしょう。そこで、これを補完するCopyOnWriteArrayListが登場しました。

読み取り操作

SynchronizedListは、読み取りと書き込み操作時に、インスタンス自体にロックがかかります。しかし、 CopyOnWriteArrayListは、すべての書き込み操作時に、元の配列にある要素をコピーして新しい一時的な配列を作成し、この一時的な配列に書き込み操作を実行した後、元の配列を更新します。これにより、読み取り操作はロックがかからないため、 SynchronizedListよりもパフォーマンスが向上します。

```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}

上記はget()メソッドですが、synchronizedがないため、ロックがかかりません。

書き込み操作

CopyOnWriteArrayListは、書き込み操作を実行する際に、明示的なロックを使用します。結局のところ、2種類のコレクションはどちらもこの操作でロックがかかります。この時、CopyOnWriteArrayListは、比較的コストの高い配列のコピー作業を行うため、書き込み作業が頻繁に行われると、パフォーマンスの問題が発生する可能性があります。

```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}

上記はadd()メソッドですが、synchronizedブロックによってロックをかけ、配列のコピー作業を実行しています。

Iterator

CopyOnWriteArrayListでiteratorを取り出す時点のコレクションデータに基づいて反復処理し、反復処理中にコレクションにデータが追加または削除された場合でも、反復処理と無関係なコピーを対象に反映されるため、同時使用に問題はありません。

CopyOnWriteArraySet

同期化されたSetを作成する方法は、以下の2つがあります。

Collections.synchronizedSet()
CopyOnWriteArraySet

メソッドの名前を見ればわかるように、CopyOnWriteArrayListと動作方法は、データ構造の特徴を除けばほぼ同じです。

読み取り操作

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}

上記はcontains()メソッドですが、CopyOnWriteArraySetは内部的にCopyOnWriteArrayListを定義し、CopyOnWriteArrayListのメソッドを使用していることがわかります。

```javascript public boolean contains(Object o) { return indexOf(o) >= 0; }

public int indexOf(Object o) { Object[] es = getArray(); return indexOfRange(o, es, 0, es.length); }

}

CopyOnWriteArrayListのcontains()メソッドを見てみると、ロックがかかっていないことがわかります。

書き込み操作

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}

add()メソッドもCopyOnWriteArrayListのメソッドを借用しています。

```javascript public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); return indexOfRange(e, snapshot, 0, snapshot.length) < 0 && addIfAbsent(e, snapshot); }

private boolean addIfAbsent(E e, Object[] snapshot) { synchronized (lock) { Object[] current = getArray(); int len = current.length; if (snapshot != current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] != snapshot[i] && Objects.equals(e, current[i])) return false; if (indexOfRange(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } }

addIfAbsent()メソッドを見てみると、書き込み操作時にロックをかけ、配列のコピーを実行しています。そのため、 CopyOnWriteArraySetもCopyOnWriteArrayListと同様に、書き込み作業はあまり行わない方が良いでしょう。

ConcurrentHashMap

同期化されたHashMapを作成する方法は、以下の2つがあります。

Collections.synchronizedMap(new HashMap<>())
ConcurrentHashMap

ConcurrentHashMapは、HashMapと同じように、HashをベースにしたMapです。synchronizedMapに比べて、より効率的な方法で同時性を保証します。

Java 8以前は、ReentrantLockを継承したSegmentを使用して、領域を区切ることで、領域ごとにロックをかける方法でした。

Java 8以降は、各テーブルバケットを独立してロックする方法を使用しています。空のバケットにノードを挿入する場合は、ロックの代わりにCASアルゴリズムを使用し、それ以外の変更は、各バケットの最初のノードを基準に部分的なロック (synchronized block)を取得することで、スレッド競合を最小限に抑え、同時性を保証します。

ConcurrentHashMapに新しいノードを挿入するputVal()メソッドのコードを見て、どのように同時性を保証しているかを確認してみましょう。ちなみに、以下のコード例はJava 11基準です。

putVal()メソッドは、大きく以下の2つのケース（分岐は合計4つ）に分けられます。

空のハッシュバケットにノードを挿入する場合
ハッシュバケットにすでにノードが存在する場合

```javascript 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; K fk; V fv; if (tab null || (n = tab.length) 0) tab = initTable(); // (1) else if ((f = tabAt(tab, i = (n - 1) & hash)) null) { // (2) if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; } else if ((fh = f.hash) MOVED) tab = helpTransfer(tab, f); else if (onlyIfAbsent // check first node without acquiring lock && fh hash && ((fk = f.key) key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; // (3) else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; // (4) if (e.hash hash && ((ek = e.key) key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; // (5) if ((e = e.next) null) { pred.next = new Node<K,V>(hash, key, value); break; } } } // (6) else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } ... } } ... }

空のハッシュバケットにノードを挿入する場合

(1) 新しいノードを挿入するために、該当バケット値（tabAt()）を取得し、空かどうかを確認します。

```javascript static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); }

(2) ノードに格納されているvolatile変数にアクセスして、既存の値（null）と比較し、同じ場合は新しいノードを保存します。同じでない場合は、forループに戻ります。この方法はCASアルゴリズムです。

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

CASアルゴリズムを使用して、原子性と可視性の問題を解決することで、同時性を保証します。

ハッシュバケットにすでにノードが存在する場合

(3) すでにノードが存在する場合は、synchronizedブロックを使用して、1つのスレッドだけがアクセスできるように制御します。この時、空でないNode<K, V>型のハッシュバケットにロックをかけるため、同じバケットにアクセスするスレッドは、Blocking状態になります。

(4) 新しいノードに置き換えます。

(5) ハッシュ衝突が発生した場合、Separate Chaingに追加します。

(6) ハッシュ衝突が発生した場合、ツリーに追加します。

参考

予想される面接の質問と回答

Vector、HashTable、Collections.SynchronziedXXXの問題点は？

Vector、HashTable、SynchronziedXxxクラスは、synchronizedメソッドまたはブロックを使用しており、 1つのロックオブジェクトを共有しています。そのため、コレクションに1つのスレッドがロックを取得した場合、他のスレッドはすべてのメソッドを使用できなくなり、Blocking状態になります。これは、アプリケーションのパフォーマンス低下につながる可能性があります。

SynchronizedListとCopyOnArrayListの違いは？

SynchronizedListは、読み取りと書き込み操作時に、インスタンス自体にロックがかかります。しかし、CopyOnArrayListは、書き込み操作時に、該当ブロックにロックをかけ、元の配列にある要素をコピーして新しい一時的な配列を作成し、この一時的な配列に書き込み操作を実行した後、元の配列を更新します。これにより、読み取り操作はロックがかからないため、SynchronizedListよりも読み取りパフォーマンスが向上します。ただし、書き込み操作は、コストの高い配列のコピー作業を行うため、SynchronizedListよりも書き込みパフォーマンスが低下します。

そのため、変更作業よりも読み取り作業が多い場合は、CopyOnArrayListを使用する方が効果的です。

SynchronizedMapとConcurrentHashMapの違いは？

SynchronziedMapは、読み取りと書き込み操作時に、インスタンス自体にロックがかかります。しかし、ConcurrentHashMapは、各テーブルバケットを独立してロックする方法を使用しています。もし、空のバケットにノードを挿入する場合、ロック（Lock）の代わりにCASアルゴリズムを使用し、それ以外の変更は、アクセスしたバケットのみにロックがかかり、スレッド競合を最小限に抑え、同時性を保証します。