Recently I run into ConcurrentSkipListMap, which is a skip list
implementation of ConcurrentNavigableMap
. Now I wonder, why it is implemented as a skip list
.
Does skip list
a "standard" implementation of concurrent navigable maps? What makes skip list
particularly good for it?
What is Skip List in Java? A skip list is a data structure that is based on probability. With a linked list, the skip list is used to hold a sorted list of components or data. It enables the pieces or data to be seen efficiently.
The ConcurrentSkipListMap is a scalable implementation of ConcurrentNavigableMap. All the elements are sorted based on natural ordering or by the Comparator passed during it's construction time.
ConcurrentSkipListMap
source code has documented the reason.
There are two reasons for taking this approach instead of the usual array-based
Here is the 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
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With