Implementation of SkipList and ConcurrentSkipListMap in Java

Introduction to the

When I first heard about SkipList, I was stunned. What? And SkipList? What the hell is this.

After continuous searching and learning, I finally understand that SkipList is originally a data structure, and ConcurrentSkipListMap and ConcurrentSkipListSet in Java are the implementation of this structure.

Let’s take a step-by-step look at SkipList and ConcurrentSkipListMap.

SkipList

Take a look at the definition of SkipList from Wikipedia:

SkipList is a hierarchical structure. At the bottom is the primitive linked List that has been sorted.

The upper layer is a hierarchical structure, with each bottom node appearing in the upper layer list with a certain probability. This probability is called P, and usually p is 1/2 or 1/4.

So let’s say we have a function f that randomly produces two numbers, 0 and 1, with the same probability, and then p is 1/2.

For each node, we do this:

We run f once, and when f=1, we insert the node into the list of the upper layer. When f=0, no insertion.

For example, the list in the figure above has 10 sorted nodes, with the first node in each layer by default. For the second node, run f=0 without insertion. For the third node, run f=1, insert the third node into Layer 1, and so on, resulting in the nodes in the Layer 1 list: 1, 3, 4, 6, 9.

Then we go up and build the layer. The result is the SkipList shown above.

Using SkipList, we built multiple lists with different sorted nodes to improve List lookup efficiency.

We can get a clearer picture from the following figure:

Each search starts from the top layer, because the top layer has the least number of nodes. If the node to be searched is between the two nodes in the list, it moves down one layer to continue the search. Finally, it finds the position to be inserted at the bottom layer, inserts the node, and then calls the probability function F again to decide whether to copy the node up.

It is essentially equivalent to a binary search, whose search time is O(logn).

ConcurrentSkipListMap

ConcurrentSkipListMap is a concurrent SkipList, so it has two characteristics, SkipList and concurrent. Let’s do it separately.

The realization of the SkipList

ConcurrentSkipListMap implements SkipList as shown above:

There are three structures in ConcurrentSkipListMap, Base Nodes,Head Nodes, and Index Nodes.

Base Nodes constitute an ordered linked list structure and are the lowest level 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; }}Copy the code

As you can see above, each Node has a K, V entry and a next pointing to the next Node.

Index Nodes are the basic nodes 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, Index<K,V> right) {
            this.node = node;
            this.down = down;
            this.right = right; }}Copy the code

We can see from the above construction that the Index Node contains the Node, in addition to the Index Node, one points to the next Node of the same layer, one points to the Node of the next layer.

Such a structure can facilitate the implementation of traversal.

Finally, 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> node, Index<K,V> down, Index<K,V> right, int level) {
            super(node, down, right);
            this.level = level; }}Copy the code

HeadIndex is similar to Index, except that there is a level field to indicate the level.

When ConcurrentSkipListMap is initialized, HeadIndex is initialized:

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

We can see that the Node in HeadIndex is a virtual Node with key= NULL and value=BASE_HEADER. Initial level=1.

The implementation of concurrent

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

Basically concurrent classes are done by UNSAFE.com pareAndSwapObject, ConcurrentSkipListMap is no exception.

Let’s say we have three nodes, B minus N minus F. Now you need to delete node N.

In the first step, use CAS to set the value of valu of n from non-null to null. At this point, any external operation will assume that the node does not exist. But those internal inserts or deletes continue to modify n’s next pointer.

In the second step, CAS is used to point n’s next pointer to a new marker node. From this point on, n’s next pointer will not point to any other node.

Let’s look at the definition of marker node:

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

We can see that the marker node is actually a node whose key is NULL and value is its own.

Third, use CAS to point the next pointer to B to f. From this point on, the n node is not accessed by any other program, which means that n can be garbage collected.

Let’s think about why we want to insert a marker node, because when we delete, we need to tell all threads that node N is ready to be deleted, because n already points to node F, and at this time, we need an intermediate node to represent the state of being deleted.

conclusion

This article starts with the SkipList data structure and explains the implementation of ConcurrentSkipListMap. I hope you enjoy it.

Welcome to pay attention to my public number: procedures those things, more wonderful waiting for you! Read more: Flydean’s blog