Implementation of concurrentskiplistmap in skiplist and Java

brief introduction

At first I heard that skiplist made me look stupid. What? And skiplist? What is this.

After continuous search and learning, I finally realized that skiplist was originally a data structure, and the concurrentskiplistmap and concurrentskiplistset in Java are the implementation of this structure.

Next, let's unveil skiplist and concurrentskiplistmap step by step.

SkipList

Let's take a look at the definition of skiplist in Wikipedia:

Skiplist is a hierarchical structure. At the bottom is the most primitive linked list that has been sorted.

Up is a layer by layer hierarchical structure, and each bottom node appears in the list of the upper layer according to a certain probability. This probability is called P, usually P takes 1 / 2 or 1 / 4.

First set a function f, which can randomly generate 0 and 1, and the probability of these two numbers is the same, then p is 1 / 2.

For each node, we operate as follows:

We run f once. When f = 1, we insert the node into the list of the upper layer. When f = 0, do not insert.

For example, there are 10 sorted nodes in the list in the above figure, and the first node is on each layer by default. For the second node, run f = 0 without inserting. For the third node, run f = 1, insert the third node into layer 1, and so on. Finally, the nodes in layer 1 list are: 1, 3, 4, 6 and 9.

Then we continue to build the layer up. Finally, the skiplist in the figure above is obtained.

By using skiplist, we build multiple lists containing different sorted nodes, so as to improve the search efficiency of lists.

We can have a clearer understanding through the following figure:

Each search starts from the top layer, because the number of nodes at the top layer is the least. If the node to be searched is between two nodes in the list, move down one layer to continue the search. Finally, find the position to be inserted at the bottom layer, insert the node, and then call the probability function f again to decide whether to copy the node upward.

It is essentially equivalent to binary search, and the time complexity of search is O (logn).

ConcurrentSkipListMap

If concurrent skiplistmap is a concurrent skiplist, it has two characteristics, skiplist and concurrent. Let's explain it separately.

Implementation of skiplist

The data structure of skiplist is explained above. Next, let's see how concurrentskiplistmap implements this skiplist:

There are three structures in concurrentskiplistmap: base nodes, head nodes and index nodes.

Base nodes constitutes an ordered linked list structure and is the bottom implementation of concurrentskiplistmap.

    static final class Node<K,V> {
        final K key;
        volatile Object value;
        volatile Node<K,V> next;

        /**
         * Creates a new regular node.
         */
        Node(K key,Object value,Node<K,V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

As can be seen above, each node is a K, V entry, and it has a next pointing to the next node.

Index nodes is the basic node for building the skiplist superstructure:

    static class Index<K,V> {
        final Node<K,V> node;
        final Index<K,V> down;
        volatile Index<K,V> right;

        /**
         * Creates index node with given values.
         */
        Index(Node<K,V> node,Index<K,V> down,V> right) {
            this.node = node;
            this.down = down;
            this.right = right;
        }
    }

From the above structure, we can see that the index node contains node nodes. In addition, the index also has two pointers, one pointing to the next node of the same layer and the other pointing to the node of the next layer.

Such a structure can facilitate the implementation of traversal.

Finally, take a look at headindex, which represents the head node:

    static final class HeadIndex<K,V> extends Index<K,V> {
        final int level;
        HeadIndex(Node<K,V> right,int level) {
            super(node,down,right);
            this.level = level;
        }
    }

Headindex is very similar to index, except that a level field is added to indicate the level.

During the initialization of concurrentskiplistmap, headindex will be initialized:

head = new HeadIndex<K,V>(new Node<K,V>(null,BASE_HEADER,null),null,1);

We can see that the node in headindex is key = null and value = base_ Virtual node of header. Initial level = 1.

Implementation of concurrent

Next, let's look at how concurrency is implemented:

Basically, concurrent classes are through unsafe Compareandswapobject, and concurrentskiplistmap is no exception.

Suppose we have three nodes, b-n-f. Now you need to delete node n.

The first step is to use CAS to set the value of n's valu from non null to null. At this time, any external operation will think that this node does not exist. However, those internal insert or delete operations will continue to modify n's next pointer.

The second step is to use CAS to point the next pointer of n to a new marker node. From this time on, the next pointer of n will not point to any other node.

Let's take a look at the definition of the marker node:

        Node(Node<K,V> next) {
            this.key = null;
            this.value = this;
            this.next = next;
        }

We can see that the marker node is actually a node with null key and value.

Step 3: use CAS to point the next pointer of B to F. From this step, n nodes will not be accessed by other programs, which means that n can be garbage collected.

Let's think about why we want to insert a marker node. This is because when deleting, we need to tell all threads that node n is ready to be deleted, because n originally points to node F. at this time, we need an intermediate node to represent the state ready to be deleted.