爲什麼將ConcurrentNavigableMap實現爲跳過列表？

Question

最近我碰到ConcurrentSkipListMap，這是的skip list執行。現在我想知道，爲什麼它被實現爲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 
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+