java - ConcurrentNavigableMap がスキップ リストとして実装されるのはなぜですか?

Question

最近、の実装であるConcurrentSkipListMapに出くわしました。今、なぜそれが として実装されているのだろうか。skip listConcurrentNavigableMapskip list

同時ナビゲート可能なマップskip listの「標準」実装はありますか? 特に良いのは何ですか？skip list

Answer 1

ConcurrentSkipListMapソースコードに理由が記載されています。

通常の配列ベースのアプローチではなく、このアプローチを採用する理由は 2 つあります。

1. 配列ベースの実装では、より複雑でオーバーヘッドが発生するようです
2. 基本リストに使用できるよりも、頻繁にトラバースされるインデックス リストに安価なアルゴリズムを使用できます。

ここにJavadocがあります

 /*
 * This class implements a tree-like two-dimensionally linked skip
 * list in which the index levels are represented in separate
 * nodes from the base nodes holding data.  **There are two reasons
 * for taking this approach instead of the usual array-based**
 * structure: 1) Array based implementations seem to encounter
 * more complexity and overhead 2) We can use cheaper algorithms
 * for the heavily-traversed index lists than can be used for the
 * base lists.  Here's a picture of some of the basics for a
 * possible list with 2 levels of index:
 *
 * Head nodes          Index nodes
 * +-+    right        +-+                      +-+
 * |2|---------------->| |--------------------->| |->null
 * +-+                 +-+                      +-+
 *  | down              |                        |
 *  v                   v                        v
 * +-+            +-+  +-+       +-+            +-+       +-+
 * |1|----------->| |->| |------>| |----------->| |------>| |->null
 * +-+            +-+  +-+       +-+            +-+       +-+
 *  v              |    |         |              |         |
 * Nodes  next     v    v         v              v         v
 * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
 * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+