[解決済み] Javaにおけるスレッドセーフセットの種類

質問

JavaでスレッドセーフなSetsを生成するには、様々な実装や方法があるようです。 いくつかの例を挙げます。

1) CopyOnWriteArraySet

2) Collections.synchronizedSet(セットセット)

3) コンカレントスキップリストセット

4) Collections.newSetFromMap(新しいConcurrentHashMap())

5) (4)と同様の方法で生成されたその他のセット

これらの例は 同時進行パターン。Java 6 の並行セット実装

どなたか、これらの例などの違いやメリット、デメリットを簡単に説明していただけませんか？私は、Java Std Docsからすべてを理解し、まっすぐに保つのに苦労しています。

どのように解決するのですか？

1. その CopyOnWriteArraySet 基本的には配列の中に要素のリストがあり、リストを変更するときに配列をコピーします。このとき実行中の反復処理や他のアクセスは古い配列で継続されるので、読み手と書き手の間で同期をとる必要はありません（ただし、書き込み自体は同期が必要です）。通常高速なセット操作（特に contains() というのも、配列は線形時間で検索されるからです。

   これは、頻繁に読み込まれ、めったに変更されない、本当に小さなセットにのみ使用します。(Swingのリスナーセットがその例ですが、これらは本当のセットではないので、いずれにせよEDTからしか使うべきではありません)。

2. Collections.synchronizedSet は、元のセットの各メソッドを単にsynchronized-blockで囲むだけです。元のセットに直接アクセスするべきではありません。これは、セットの2つのメソッドを同時に実行できないことを意味します（一方は他方が終了するまでブロックされます）。これはスレッドセーフですが、複数のスレッドがセットを使用している場合は同時実行ができません。イテレータを使用する場合、イテレータ呼び出しの間にセットを変更するときに ConcurrentModificationExceptions を回避するために、通常は外部で同期を取る必要があります。 性能は元のセットの性能と同じになります（ただし、同期のオーバーヘッドがあり、同時に使用するとブロックされます）。

   同時実行性が低く、すべての変更が他のスレッドからすぐに見えることを確認したい場合に使用します。

3. ConcurrentSkipListSet は、同時進行の SortedSet の実装で、ほとんどの基本操作はO(log n)で可能です。追加/削除と読み込み/反復を同時に行うことができ、反復はイテレータが作成されてからの変更について伝えることもできますし、伝えないこともできます。一括操作は単純に複数の単一呼び出しであり、アトミックに行われるわけではありません - 他のスレッドはその一部しか観察できないかもしれません。

   明らかに、これは要素に何らかの総体的な秩序がある場合にのみ使用することができます。 これは、あまり大きくないセットで、高い同時実行性が必要な場合に理想的な候補に見えます（O(log n)のため）。

4. については ConcurrentHashMap (およびそこから派生するセット): ここで最も基本的なオプションは、(平均して、高速で優れた hashCode() )で、HashMap/HashSetと同様にO(1) (ただし、多くのキーが同じハッシュコードを持つ場合はO(n)に退化する可能性がある)で実現できる。書き込みの並行性には制限があり（テーブルはパーティション化されており、書き込みアクセスは必要なパーティションで同期される）、読み込みアクセスは自身と書き込みスレッドで完全に同時進行する（ただし、現在書き込まれている変更の結果はまだ見ていないかもしれない）。イテレータは、それが作成されてからの変更を見ることも見ないこともあり、バルク操作はアトミックではありません。 リサイズには時間がかかる（HashMap/HashSetと同様）ので、作成時に必要なサイズを推定してこれを避けるようにする必要があります（3/4がいっぱいになるとリサイズされるので、その約1/3を使用することになります）。

   大きなセットと優れた（そして高速な）ハッシュ関数があり、マップを作成する前にセットのサイズと必要な同時実行性を見積もることができる場合に使用します。

5. 他の並列マップの実装はありますか？