Concurrentskiplistmap -- principle of table skipping

In order to elicit ConcurrentSkipListMap, First, let's briefly understand what is skip table .

For single chain table , Even if the linked list is ordered , If you want to find some data in it , You can only traverse the linked list from beginning to end , In this way, the efficiency will be very low , The jump watch is different . Jump table is a kind of data structure that can be used to find quickly , It's kind of like a balance tree . They can all find elements quickly . But an important difference is ： The insertion and deletion of the balance tree may lead to a global adjustment of the balance tree ; And the insertion and deletion of the jump table , You only need to operate on parts of the entire data structure . The advantage of this is ： In the case of high concurrency , Need a global lock , To ensure the thread safety of the whole balance tree ; And for jump tables , Then only part of the lock is needed . such , In a highly concurrent environment , You can have better performance . In terms of query performance , The time complexity of the jump table is O(logn), So in concurrent data structures ,JDK Use a jump table to implement a Map.

Essence of skip table , yes Multiple linked lists are maintained at the same time , And linked lists are hierarchical ：

2 Level index jump table

The lowest linked list , All elements in the jump table are maintained , Each layer of linked list , Are subsets of the lower layer .

All the elements of the linked list in the jump list are sorted . When looking for , You can start with the top-level list . Once it is found that the element being searched is larger than the value in the current linked list , Will go to the next level of linked list to continue looking for . That is to say, during the search process , The search is leaping . As shown in the figure above , Look up elements in the jump table 18.

Look up elements in the jump table 18

lookup 18 When , Originally, you need to traverse 18 Time , Now it's just a matter of 7 Next time . When the length of the linked list is relatively large , Build index , The improvement of search efficiency will be very obvious .

It's easy to see from above , Jump table is an algorithm that uses space to change time .

Use the jump table to achieve Map, And using hash algorithm to achieve Map The other difference between them is ： Hashing doesn't hold the order of the elements , And all the elements in the jump table are sorted . therefore , When traversing the jump table , You'll get an orderly result . therefore , If your application needs order , So watch jumping is your best choice .
JDK The class that implements this data structure in is ConcurrentSkipListMap.