[解決済み] ConcurrentSkipListSetはどのような場合に有効ですか？

質問

Java 6 APIでこのデータ構造を見たばかりですが、いつ役に立つリソースになるのか興味があります。私はscjpの試験勉強をしていますが、Kathy Sierraの本では取り上げられておらず、模擬試験の問題でも言及されています。

解き方は？

コンカレントスキップリストセット と コンカレントスキップリストマップ は、複数のスレッドからアクセスされるソートされたコンテナが必要な場合に便利です。 これらは本質的に、並行処理コードのための TreeMap と TreeSet に相当します。

JDK 6 の実装は 高性能な動的ロックフリーハッシュテーブルとリストベースセット を使って、スキップリストに対する多くの操作をアトミックに実装できることを示した、IBM の Maged Michael 氏によるものです。 コンペア＆スワップ(CAS) という演算があります。 これらの操作はロックフリーなので synchronized (ほとんどの操作で) これらのクラスを使用する場合。

現在 赤黒い木 ベースの並列 Map/Set 実装を Java で実現しました。 少し文献に目を通したところ カップル 論文 は、同時実行RBツリーがスキップリストより優れていることを示しましたが、これらのテストの多くは トランザクションメモリ これは、今のところ主要なアーキテクチャでハードウェア的にサポートされていません。

JDKがスキップリストを採用したのは、その実装がよく知られていたことと、ロックフリーを実現するのが簡単で移植性が高い（CASを使用する）ためだと推測しています。 もし、明確にしたい人がいれば、ぜひ教えてください。 私は興味があります。