Dlaczego funkcja ConcurrentNavigableMap została zaimplementowana jako lista pominięć?

Question

Niedawno natknąłem się na ConcurrentSkipListMap, która jest implementacją skip list implementacji ConcurrentNavigableMap. Teraz zastanawiam się, dlaczego jest on implementowany jako skip list.

Czy skip list jest "standardową" implementacją współbieżnych map nawigacyjnych? Co sprawia, że ​​skip list jest dla niego szczególnie dobre?

Answer 1

kod źródłowy udokumentował przyczynę.

Istnieją dwa powody podjęcia tej metody zamiast implementacji zwykle tablica oparte

1. Array opartych wydają się spotkać większą złożoność i napowietrznych
2. możemy użyć tańszych algorytmów za mocno pokonywany indeksu wymienia niż można wykorzystać do listy bazowych

Oto 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 
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+