Warum wird ConcurrentNavigableMap als Überspringungsliste implementiert?

Question

Vor kurzem lief ich in ConcurrentSkipListMap, die eine skip list Implementierung von ConcurrentNavigableMap ist. Jetzt frage ich mich, warum es als skip list implementiert ist.

Ist skip list eine "Standard" -Implementierung von gleichzeitige navigierbare Karten? Was macht skip list besonders gut dafür?

Answer 1

ConcurrentSkipListMap Quellcode hat den Grund dokumentiert.

Es gibt zwei Gründe für diesen Ansatz statt der üblichen Array-basierten

1. Array basierte Implementierungen scheinen mehr Komplexität und Kopf
2. Wir billiger Algorithmen für die stark befahrenen Index verwenden können, begegnen für die Basislisten

Hier listet als verwendet werden, ist die 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 
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+