Skip list and concurrentskiplistmap

1、 Skip list

For a single linked list, even if the linked list is ordered, if you want to find a data in it, you can only traverse the linked list from beginning to end. In this way, the efficiency will naturally be very low, and the jump table will be different. Jump table is a data structure that can be used to quickly find, which is a bit similar to balanced tree. They can quickly find elements. But an important difference is that the insertion and deletion of the balance tree are likely to lead to a global adjustment of the balance tree; To insert and delete a jump table, you only need to operate part of the whole data structure. The benefits of this are: in the case of high concurrency, a global lock is required to ensure the thread safety of the whole balance tree; For meter hopping, only partial locking is required. In this way, you can have better performance in a high concurrency environment. In terms of query performance, the time complexity of jump table is O (logn).

The essence of a jump list is that multiple linked lists are maintained at the same time, and the linked list is hierarchical:

The linked list at the lowest level maintains all the elements in the hop list. Each linked list at the upper level is a subset of the lower level.

The elements of each layer of the linked list in the jump list are orderly. When searching, you can start from the top-level linked list. Once it is found that the searched element is greater than the value in the current linked list, it will be transferred to the next linked list to continue searching. In other words, in the search process, the search is jumping. As shown in the above figure, find element 18 in the skip table:

You can see that when looking for 18, you need to traverse 12 times, but now you only need 7 times. When the length of the linked list is large, the improvement of search efficiency will be very obvious when building the index.

It is easy to see from the above that table hopping is an algorithm that uses space for time.

2、 Concurrentskiplistmap

Concurrentskiplistmap is a thread safe non blocking map based on jump table. It requires that the key and value in the map cannot be null. Compared with the map implemented by hash, all elements in the hop table are orderly; Compared with treemap with red black tree structure, concurrentskiplistmap is thread safe.

Concurrentskiplistmap is suitable for high concurrency scenarios. Under a certain amount of data, the more concurrent threads, the more the concurrentskiplistmap can reflect its query advantages.

The access performance of concurrentskipplistmap is inferior to that of concurrenthashmap (under the condition of 16000 data in 4 threads, the access speed of concurrenthashmap is about 4 times that of concurrentskipplistmap). Its advantage is that all elements in the hop table are orderly.

In the case of non multithreading, treemap should be used as much as possible. In addition, for parallel programs with relatively low concurrency, you can use collections Synchronized SortedMap wraps the treemap to ensure thread safety.

3、 Concurrentskiplistmap data structure

The entire data structure of concurrentskiplistmap can be analyzed from the source code as follows:

Let's take a look at the class information of headindex, index and node respectively:

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

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

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

You can see that the index contains the reference of the node and points to their respective index fields with right and down references respectively; Headindex inherits from index. As the head node of the index, it maintains the concept of level in the hop table; The node stores the actual key and value information, and uses the next reference to build a single linked list.

For detailed source code analysis, see this article: https://www.jianshu.com/p/2075a76a43a3

4、 Concurrentskiplistmap example

The following is an example of "multiple threads operate simultaneously and traverse the map" to verify the thread safety of concurrentskiplistmap:

public class ConcurrentSkipListMapTest {

    //private static Map<String,String> MAP = new TreeMap<String,String>();
    private static Map<String,String> MAP = new ConcurrentSkipListMap<String,String>();

    public static void main(String[] args) {
        // 同时启动两个线程对map进行操作！
        new MyThread("A").start();
        new MyThread("B").start();
    }

    private static void printAll() {
        String key,value;
        Iterator iterator = MAP.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            key = (String) entry.getKey();
            value = (String) entry.getValue();
            System.out.print("(" + key + "," + value + "),");
        }
        System.out.println();
    }

    private static class MyThread extends Thread {
        MyThread(String name) {
            super(name);
        }

        @Override
        public void run() {
            int i = 0;
            while (i++ < 6) {
                // "线程名" + "序号"
                String val = Thread.currentThread().getName() + i;
                MAP.put(val,"0");
                printAll();
            }
        }
    }
}

5、 Concurrentskiplistset

Almost all sets in Java are implemented internally with a map, because keyset () in the map is a set set, and value is a false value. All use the same object.

The concurrentskiplistset is no exception. It is internally implemented using the concurrentskiplistmap set and uses its addifabsent () method to remove duplicate elements.