Concurrentskiplistmap of Java concurrency collection_ Power node Java college sorting

Introduction to concurrentskiplistmap

Concurrentskiplistmap is a thread safe and ordered hash table, which is suitable for high concurrency scenarios.

Concurrentskiplistmap and treemap, although they are ordered hash tables. However, first, their thread safety mechanisms are different. Treemap is non thread safe, while concurrentskiplistmap is thread safe. Second, the concurrentskiplistmap is implemented through the jump table, while the treemap is implemented through the red black tree.

As for the skip list, it is an alternative data structure of the balance tree. However, unlike the red black tree, the implementation of the tree balance by the skip list is based on a randomized algorithm, which means that the insertion and deletion of the skip table are relatively simple.

Principle and data structure of concurrentskiplistmap

The data structure of concurrentskiplistmap is shown in the following figure:

explain:

First, take the data "7,14,21,32,37,71,85" sequence as an example to briefly explain the skip table.

The hop table is divided into many levels, and each layer can be regarded as an index of data. The meaning of these indexes is to speed up the speed of finding data in the hop table. The data of each layer is ordered, the data of the previous layer is a subset of the data of the next layer, and the first layer (Level 1) contains all the data; The higher the level, the greater the jump, and the less data it contains. The jump table contains a header. When searching for data, it searches from top to bottom and from left to right. Now take "need to find the node with the value of 32" as an example to compare the jump list with the general linked list.

Case 1: find the "32" node in the linked list

The path is shown in figure 1-02 below:

4 steps are required (the red part indicates the path).

Case 2: find the "32" node in the skip table

The path is shown in figure 1-03 below:

When the path on the index vertical line is ignored, only 2 steps are required (the red part indicates the path).

Let's talk about the data structure of concurrentskiplistmap in Java. (01) concurrentskiplistmap inherits from the abstractmap class, which means that it is a hash table. (02) index is the internal class of concurrentskiplistmap, which corresponds to the "index in jump table". Headindex inherits from index. Concurrentskiplistmap contains an object head of headindex, which is the "header of jump table". (03) index is the index in the jump table, which includes "right" of the right index, "down" of the lower index and "node of the hash table". Node is the object of node, and node is also an internal class in concurrentskiplistmap.

List of concurrentskiplistmap functions

Next, analyze the concurrentskiplistmap from the three aspects of adding, deleting and obtaining.

1. Add

Next, take put (k key, V value) as an example to explain the addition method of concurrentskiplistmap.

In fact, put () adds a key value pair to the concurrentskiplistmap through doput ().

The source code of doput() is as follows:

Note: doput() is used to add key value pairs to the "skip table". To figure out doput (), we must first figure out its main part -- we simply consider "adding key value to the jump table in the case of single thread", that is, ignoring "multi thread related content". Its process is as follows:

Step 1: find the "insertion position". That is, find "key's predecessor node (b)" and "key's successor node (n)"; Key is the key to insert the node.

Step 2: create and insert a new node. That is, create a new node Z (the node corresponding to the key) and insert the new node Z into the "hop table" (set the successor node of "B" to Z and the successor node of Z to n).

Step 3: update the skip table. That is, randomly obtain a level, and then insert node Z in each layer between layer 1 and level of the "jump table"; No more nodes are inserted above the level. If the level value is greater than "skip table level", a new level will be created.

The "corresponding reduced doput () code" of the trunk part is as follows (for reference only):

After sorting out the trunk, the remaining work is relatively simple. Mainly the specific implementation of the corresponding algorithm in the above steps, as well as the processing of multithreading related situations!

2. Delete

Next, take remove (object key) as an example to describe the deletion method of concurrentskiplistmap.

In fact, remove () deletes the key value pair corresponding to the key in the concurrentskiplistmap through doremove ().

The source code of doremove() is as follows:

Note: the purpose of doremove() is to delete nodes in the hop table. Like doput (), we focus on the main part of doremove (). After understanding the main part, the rest is very easy to understand. The following is the "steps to delete key value pairs in the hop table in the case of single thread":

Step 1: find the "location of the deleted node". That is, find "previous node (b) of key", "node (n) corresponding to key" and "subsequent node F of n"; Key is the key to delete the node.

Step 2: delete the node. That is, remove the node n corresponding to the "key" from the hop table -- set the "subsequent node of B" to "F"!

Step 3: update the skip table. That is, traverse the skip table and delete the "key node" (if any) of each layer. If the "key node" is deleted, the skip table level needs - 1; Then perform the corresponding operation!

The trunk part "corresponding reduced doremove() code" is as follows (for reference only):

3. Acquisition

Next, take get (object key) as an example to describe the acquisition method of concurrentskiplistmap.

The source code of doget is as follows:

Note: doget() finds and returns the node through findnode().

Note: findnode (key) is used to return the node corresponding to the key in the hop table; If it exists, the node is returned; if it does not exist, null is returned. First clarify the main part of the function, that is, put aside the "multi-threaded related content" and simply consider the algorithm of obtaining nodes from the hop table in the case of single thread.

Step 1: find the "location of the deleted node". Locate the hierarchy of the key and find the successor node (b) of the key according to findpredecessor(), and then find the successor node n of B.

Step 2: locate the "key corresponding node" according to "key's predecessor node (b)" and "key's successor node (n)". Specifically, by comparing the size of "key value of n" and "key". If equal, then n is the key to find.

Concurrentskiplistmap example

(a) operation result:

Result description:

In the sample program, start two threads (thread a and thread b) to operate the concurrentskiplistmap respectively. For thread a, it will first obtain "thread name" + "sequence number", then insert the string as the key and "0" as the value into the concurrentskiplistmap; Next, traverse and output all the elements in the concurrentskiplistmap. The operation of thread B is the same as that of thread a, except that the name of thread B is different from that of thread a.

When the map is a concurrentskiplistmap object, the program can run normally. If the map is changed to treemap, the program will generate a concurrentmodificationexception.

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.