Почему ConcurrentNavigableMap реализован как список пропусков?

Question

Недавно я столкнулся с ConcurrentSkipListMap, который является skip list внедрением ConcurrentNavigableMap. Теперь интересно, почему он реализован как skip list.

skip list «стандартная» реализация одновременная судоходная карты? Что отличает skip list?

Answer 1

ConcurrentSkipListMap Исходный код документировал причину.

Есть две причин для принятия такого подхода вместо реализаций на основе обычного массива на основе

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