An introduction to the
(1) What is a skip list?
The so-called skip list is to add multiple indexed linked lists on the basis of the common linked list, so that when searching, you can jump between the index linked lists of different levels up and down to achieve the purpose of fast searching.
Of course, this may sound abstract, but let me illustrate it briefly with a picture.
As you can see from the diagram above, skip lists have three different types of objects.
I) Data linked list in blue:
The lowest level of the diagram is the actual data linked list, where each Node has three fields:
- Key: indicates the key of the key-value pair
- Value: value of a key value pair
- Next: points to the next data node
In addition, linked lists have another feature, that is, they are stored sequentially, through insertion processing.
Ii) Indexed linked lists in orange:
Looking at the linked index list in the figure, we can see that it is hierarchical and points to both its lower index nodes and the index nodes on the right of the same level. Therefore, each Index node also has three fields:
- Node: in the same column
The Index nodeThey all point to the same thing at the bottomThe Node Node, the purpose is to determine which data node it corresponds to through the index node at any time - Down: indicates the index node of the next layer
- Right: points to the index node on the right of the same layer
Iii) Linked list of header indexes in purple:
A closer look at the diagram above shows that the header index list is essentially an index list, with a field representing the current horizontal level of the chain added to the regular index list. Therefore, each HeadIndex node needs to be represented by four fields:
- Level: level of the current indexed list, counting from 1
- Node: Points to the base in the lower left corner
The Node NodetheThe Node NodeIt’s just symbolic, so there’s no KEY - Down: indicates the header index node at the next level
- Right: points to the index node on the right of the same layer
(2) Skip list search
Again using the diagram above, let’s look at two typical lookup examples.
I) Search for data node D:
Obviously, start with the HeadIndex node in the upper left.
- The index node on the right of the third layer is
Index[G], its data node is greater than D, so it cannot be moved to the rightIndex[G]; - Down to the second floor
HeadIndex nodeIf I keep looking to the right,Index[B]The KEY of the data node is B, less than D, so move to the second layerIndex[B]; - Put the second layer again
Index[B]With the right of theIndex[G]Comparison, found that can not continue to move to the right; - Down to the first floor
Index[B]And then follow the one on the rightIndex[F]Comparison, found that can not continue to move to the right; - Then, there are no other indexed lists below, so go right to D on the linked list and return the result.
Ii) Search for data node H:
After looking at the examples above, you should have seen that finding data in a skip list generally requires the following steps:
- From the top left
HeadIndex nodeStart a search; - First, search right in the horizontal linked list for the index node that is less than the maximum value of the target node (PS: if the data node corresponding to this index node is the node we are looking for, then return directly);
- If a lower level index exists on the node after the above step, move down one step;
- Repeat steps 2 and 3 until there are no lower level index nodes below.
- Finally, continue to the right on the linked list to find the target node, and return the final result.
Following the general steps described above, let’s use a diagram to see what steps are required to find H.
Finally, the diagram I drew above is pretty clear, so I won’t say much more about literal statements.
(3) Skip list insertion
As can be seen from the diagram above, skip lists are mainly divided into two parts: data linked list and index linked list. Therefore, when inserting data, the first thing you need to do is to insert the data into the linked list, and then set a reasonable index for the newly inserted data.
Using the example above, let’s assume that node B is newly inserted into the skip list. Let’s take a look at the steps needed to complete the insertion process.
I) Insert data into data linked list:
Because skip lists add multiple levels of indexed lists on the basis of ordinary linked lists for fast lookup purposes, its core function still has a data list to store data, so the first step we need to do is to insert data into the data list in the appropriate location.
With the query flow described above, the implementation of this step is very simple and requires the following two steps:
- Find the largest data node smaller than the node to be inserted.
- Insert the new node into the linked list.
Ii) Establish reasonable indexes at random levels:
After inserting the data into the linked list, all we need to do is set up the appropriate index for the new data node. There is no standard answer to this step, just create a random level of index nodes for the new nodes, preferably evenly distributed.
In the ConcurrentSkipListMap source code for Java8, it sets the policy as follows:
- Generate a random integer (which can be an integer or a negative number);
- Check whether the highest bit and lowest bit of the binary representation of the random number are 1 at the same time. If they are both 1, there is no need to build an index for this node. Otherwise, go through the process of building an index node (00, 01, 10, 11, therefore, there is a 3/4 probability of creating an index).
- Set the default index level to 1, then determine the binary representation of the above random number from the second right there are a number of 1, the default level (1) before the number of 1 increment several times as the final index level of the new node. Of course, if this number is too large to exceed the maximum level of the original index list, the new node’s index level is set to the maximum level of the original index list plus one;
- The loop initializes the index node of the column added by the new node and completes this step.
Iii) Associate the newly created index node to the original index linked list:
After initializing the index nodes in the previous step, all you need to do in this step is to associate each level of index nodes with the original horizontal index list. So it can be done in the following four steps:
- From the top left
HeadIndex nodeStart a search; - Find the top-level index node of the new node according to the level and the KEY of the new node, and add the top-level index node of the new node into the horizontal index list of this layer.
- Proceed to insert the bottom index node of the topmost index node of the new node into its horizontal linked list. Similarly, the index node on the left of the new node is searched according to the current level and the KEY of the new node, and then the index node on this layer of the new node is added to the horizontal index list.
- Repeat steps 2 and 3 above until all the index nodes of the new node are associated with the original horizontal index list.
(4) Skip list deletion
Skip list deletion is actually the reverse operation of the insert process, so understand how to insert, naturally know how to delete. Of course, the main steps are also three:
- Find the data node to delete;
- Remove the data node from the data link list;
- Looping removes all levels of the index nodes for this node and reassociates the index nodes.
Java implementation of skip list
Above, I have spent a lot of time describing the basic operation steps of skip lists. Below, I will present a skip list implemented in Java. For details of the logic, please refer to the above instructions and comments in the code.
Full source address: gitee.com/zifangsky/D…
package cn.zifangsky.skiplist;
import cn.zifangsky.hashtable.Map;
import java.text.MessageFormat;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.BiConsumer;
/** * jump table **@author zifangsky
* @date 2019/8/8
* @since1.0.0 * /
public class SkipListMap <K extends Comparable.V> implements Map<K.V> {
/** * Single node information */
static class Node<K extends Comparable.V> {
/** * key */
final K key;
/** * value */
volatile Object value;
/** * next node */
volatile Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
public Node(K key, Object value, Node<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
/** * returns whether "BASE_HEADER node at the bottom left of the list" */
boolean isBaseHeader(a){
return value == BASE_HEADER;
}
/** * Returns whether it is a data node */
V getValidValue(a) {
Object v = value;
if (v == this || this.isBaseHeader()) {
return null;
}
return (V)v;
}
/** * Compares the KEY size with another node *@paramO Another node *@return int
*/
int compareKeyTo(Node<K, V> o){
return this.key.compareTo(o.key);
}
/** * Compare the current node KEY to another node KEY *@paramKey Indicates the key * of another node@return int
*/
int compareKeyTo(K key){
return this.key.compareTo(key);
}
@Override
public final String toString(a) {
return key + "=" + value;
}
@Override
public final boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null|| getClass() ! = o.getClass()) {return false; } Node<? ,? > node = (Node<? ,? >) o;return SkipListMap.equals(key, node.key) &&
SkipListMap.equals(value, node.value);
}
/** ** take xor */ of the hashCode of key and value
@Override
public final int hashCode(a) {
returnSkipListMap.hashCode(key) ^ SkipListMap.hashCode(value); }}/** * index node */
static class Index<K extends Comparable.V> {
/** * The lowest data node that the index points to */
final Node<K, V> node;
/** ** * index node */
final Index<K, V> down;
/** ** the right index node */
volatile Index<K, V> right;
public Index(Node<K, V> node, Index<K, V> down) {
this(node, down, null);
}
public Index(Node<K, V> node, Index<K, V> down, Index<K, V> right) {
this.node = node;
this.down = down;
this.right = right; }}/** * header index node */
static class HeadIndex<K extends Comparable.V> extends Index<K.V>{
/** * used to identify the level of the current index */
int level;
public HeadIndex(Node<K, V> node, Index<K, V> down, Index<K, V> right, int level) {
super(node, down, right);
this.level = level; }}/* ---------------- Fields -------------- */
/** * Initial first node */
private static final Object BASE_HEADER = new Object();
/** * the default level of the first level */
public static final int DEFAULT_LEVEL = 1;
/** * the top-level header of the entire skip list */
private transient volatile HeadIndex<K, V> head;
/** * index level */
private volatile int level;
public SkipListMap(a) {
this.initialize();
}
public static int hashCode(Object o) {
returno ! =null ? o.hashCode() : 0;
}
public static boolean equals(Object a, Object b) {
return(a == b) || (a ! =null && a.equals(b));
}
@Override
public int size(a) {
int count = 0;
for(Node<K, V> temp = this.findFirst(); temp ! =null; temp = temp.next){
if(temp.getValidValue() ! =null){ count++; }}return count;
}
@Override
public boolean isEmpty(a) {
return this.findFirst() == null;
}
@Override
public boolean containsKey(K key) {
return this.getNode(key) ! =null;
}
@Override
public V get(K key) {
Node<K, V> temp;
return (temp = this.getNode(key)) ! =null ? (V) temp.value : null;
}
@Override
public void put(K key, V value) {
this.putVal(key, value);
}
@Override
public void remove(K key) {
this.removeVal(key);
}
@Override
public void clear(a) {
this.initialize();
}
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {}/** * format traversal output */
public void forEach(a) {
HeadIndex<K, V> headIdx = this.head;
//1. Get an array of index nodesIndex<? ,? >[] idxArr =newIndex<? ,? > [this.level];
while(headIdx ! =null){
idxArr[headIdx.level-1] = headIdx.right;
headIdx = (HeadIndex<K, V>) headIdx.down;
}
//2. Get the first data node
Node<K, V> node = this.findFirst();
//3. Traverse the index node
for(int i = this.level; i > 0; i--){
System.out.print(MessageFormat.format("HeadIdx[level={0}]", i));
if(idxArr.length == this.level){ Index<? ,? > idx = idxArr[i -1];
Node<K, V> tmpNode = node;
// The index list is traversed based on the linked list. If a data node does not have an index, a placeholder is used instead
while(tmpNode ! =null) {if(idx ! =null && tmpNode.equals(idx.node)){
System.out.print(MessageFormat.format(", Idx[key={0}]", tmpNode.key));
idx = idx.right;
}else{
System.out.print(", Idx[null]");
}
tmpNode = tmpNode.next;
}
}
System.out.print("\n");
}
//4. Iterate over the data node
System.out.print("HeadNode[BASE_HEADER]");
while(node ! =null){
System.out.print(MessageFormat.format(", Node[key={0}, value={1}]", node.key, node.value));
node = node.next;
}
System.out.print("\n");
}
/** * initializes */
private void initialize(a) {
level = DEFAULT_LEVEL;
head = new HeadIndex<K, V>(new Node<K, V>(null, BASE_HEADER, null),
null.null, DEFAULT_LEVEL);
}
/** * get the first data node */
private Node<K, V> findFirst(a){
Node<K, V> preNode = this.head.node;
// Nodes in the data section
Node<K, V> node = preNode.next;
if(node ! =null) {return node;
}else{
return null; }}/** ** Removes a key pair */
private void removeVal(K key){
//1. Delete data nodes
//1.1 Prefetch key data node
Node<K, V> preNode = this.findPreNode(key);
// Next data node
Node<K, V> node = preNode.next;
//1.2 Check whether it is the node we are looking for
if(node == null|| node.key.compareTo(key) ! =0) {return;
}
//1.3 Remove the data node from the list
preNode.next = node.next;
//2. Delete the index node
Index<K, V> preLevelIdx = this.findDownPreIdx(this.head, node);
if(preLevelIdx ! =null) {//2.1 Obtain the index node of the target node
Index<K, V> levelIdx = preLevelIdx.right;
2.2 Re-associate indexed linked lists
preLevelIdx.right = levelIdx.right;
//2.3 Continue to delete the underlying index Node
while(preLevelIdx ! =null){
preLevelIdx = this.findDownPreIdx(preLevelIdx, node);
if(preLevelIdx ! =null) { levelIdx = preLevelIdx.right; preLevelIdx.right = levelIdx.right; }}}}/** * Find the corresponding data node by key */
private Node<K, V> getNode(K key){
//1. Obtain the front data node of the key
Node<K, V> preNode = this.findPreNode(key);
// Next data node
Node<K, V> node = preNode.next;
//2. Check if it is the node we are looking for
if(node ! =null && node.key.compareTo(key) == 0) {return node;
}else{
return null; }}/** * stores a key-value pair */
private void putVal(K key, V value){
//1. Obtain the front data node of the key
Node<K, V> preNode = this.findPreNode(key);
// Get the rear node as the rear node of the new node
Node<K, V> nextNode = preNode.next;
// If duplicate nodes are found, replace the values and return
if(nextNode ! =null && nextNode.compareKeyTo(key) == 0){
nextNode.value = value;
preNode.next = nextNode;
return;
}
//2. Create a data node
Node<K, V> newNode = new Node<>(key, value);
//3. Mount the new node to the linked list
newNode.next = nextNode;
preNode.next = newNode;
//4. Set the index of the new node
this.createNodeIndex(newNode);
}
/** * Set the index of the newly inserted data node *@paramNewNode Newly inserted into the list of data nodes */
private void createNodeIndex(Node<K, V> newNode){
1. Generate a random integer
int rnd = ThreadLocalRandom.current().nextInt();
//2. If the highest bit and the lowest bit are both 1, insert the linked list directly (1/4 probability), and create index nodes for others
if((rnd & 0x80000001) = =0){
HeadIndex<K, V> headIdx = this.head;
Index<K, V> idx = null;
// The level of the index node
int level = 1, maxLevel = headIdx.level;
//2.1 Determine which level of index nodes should be created (counting the number of consecutive 1 nodes from the second on the right)
while (((rnd = rnd >>> 1) & 1) = =1){
level++;
}
//2.2 Creating an INDEX Node
// If the calculated level does not exceed the original maximum level, then loop through the index node directly, otherwise need to create a new level at the top
if(level <= maxLevel){
for(int i = 1; i <= level; i++){
idx = newIndex<>(newNode, idx); }}else{
// Create a new index node at the top level
level = maxLevel + 1;
this.level = level;
//2.2.1 Creating an INDEX Node
for(int i = 1; i <= level; i++){
idx = new Index<>(newNode, idx);
}
2.2.2 Resetting the header index for each level
HeadIndex<K, V> newHeadIdx = new HeadIndex<>(headIdx.node, headIdx, null, level);
HeadIndex<K, V> levelHeadIdx = newHeadIdx;
for(int i = level; i >= 1; i--){
levelHeadIdx.level = i;
levelHeadIdx = (HeadIndex<K, V>) levelHeadIdx.down;
}
// Create a new top-level header node
this.head = newHeadIdx;
headIdx = newHeadIdx;
}
//2.3 Associate the newly created index node with the original index node
Index<K, V> levelIdx = idx;
Index<K, V> preLevelIdx = this.findDownPreIdx(headIdx, headIdx.level, level, idx.node);
// Horizontally associate index nodes
levelIdx.right = preLevelIdx.right;
preLevelIdx.right = levelIdx;
for(int i = level; i > 1; i--){
levelIdx = levelIdx.down;
preLevelIdx = this.findDownPreIdx(preLevelIdx, i, (i - 1), levelIdx.node);
// Horizontally associate index nodeslevelIdx.right = preLevelIdx.right; preLevelIdx.right = levelIdx; }}}/** * finds the underlying index node of the specified index node, returns null * if no@paramCurrent Current index position *@paramExpectedNode The target node *@return cn.zifangsky.skiplist.SkipListMap.Index<K, V>
*/
private Index<K, V> findDownPreIdx(Index<K, V> current, Node<K, V> expectedNode){
Index<K, V> currentIdx = current;
// Right index node
Index<K, V> rightIdx;
// Right data node
Node<K, V> rightNode;
// Keep searching right and down for the leading index node of the specified level
while(currentIdx ! =null) {//1. Move index to right
while (true){
rightIdx = currentIdx.right;
if(rightIdx == null) {break;
}
rightNode = rightIdx.node;
// If the right index node is still to the left of the target node, move the index to the right
if(rightNode.compareKeyTo(expectedNode) < 0){
currentIdx = currentIdx.right;
}else if(rightNode.compareKeyTo(expectedNode) == 0) {return currentIdx;
}else{
break; }}//2. Move the index down one step
currentIdx = currentIdx.down;
}
return null;
}
/** * finds the underlying index node * at the specified level@paramCurrent Current index position *@paramCurrentLevel indicates the currentLevel *@paramExpectedLevel The level to be searched *@paramExpectedNode The target node *@return cn.zifangsky.skiplist.SkipListMap.Index<K, V>
*/
private Index<K, V> findDownPreIdx(Index<K, V> current, int currentLevel,
int expectedLevel, Node<K, V> expectedNode){
Index<K, V> currentIdx = current;
// Right index node
Index<K, V> rightIdx;
// Right data node
Node<K, V> rightNode;
// Keep searching right and down for the leading index node of the specified level
while (currentLevel >= 1) {//1. Move index to right
while (true){
rightIdx = currentIdx.right;
if(rightIdx == null) {break;
}
rightNode = rightIdx.node;
// If the right index node is still to the left of the target node, move the index to the right
if(rightNode.compareKeyTo(expectedNode) < 0){
currentIdx = currentIdx.right;
}else{
break; }}//2. Move the index down one step
if(currentLevel > expectedLevel){
currentLevel = (currentLevel -1);
currentIdx = currentIdx.down;
}else{
break; }}return currentIdx;
}
/** * finds * before the specified KEY@param key KEY
* @return cn.zifangsky.skiplist.SkipListMap.Node<K,V>
*/
private Node<K, V> findPreNode(K key){
Index<K, V> currentIdx = head;
// Index node
Index<K, V> downIdx;
// Right index node
Index<K, V> rightIdx;
// Right data node
Node<K, V> rightNode;
// Keep searching right and down for the front data node of the specified KEY
while (true) {//1. Move index to right
while (true){
rightIdx = currentIdx.right;
if(rightIdx == null) {break;
}
rightNode = rightIdx.node;
// If the right index node is still to the left of the target node, move the index to the right
if(rightNode.compareKeyTo(key) < 0){
currentIdx = currentIdx.right;
}else{
break;
}
}
downIdx = currentIdx.down;
//2. If the index node below is not empty, move the index down one step
if(downIdx ! =null){
currentIdx = downIdx;
}else{
break; }}//3. Move further to the right on the data link
Node<K, V> idxNode = currentIdx.node;
while (true){
rightNode = idxNode.next;
// If the right data node is still to the left of the target node, move the index to the right
if(rightNode == null || rightNode.compareKeyTo(key) >= 0) {break;
}else{ idxNode = idxNode.next; }}returnidxNode; }}Copy the codeTest cases:
@Test
public void test(a){
SkipListMap<String,Integer > skipListMap = new SkipListMap<>();
/ / 1.1 insert
skipListMap.put("A".1);
skipListMap.put("B".2);
skipListMap.put("J".10);
skipListMap.put("D".4);
skipListMap.put("C".3);
skipListMap.put("E".5);
skipListMap.put("I".9);
skipListMap.put("F".6);
skipListMap.put("H".8);
skipListMap.put("G".7);
/ / 1.2 traversal
skipListMap.forEach();
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
/ / 2.1 lookup
System.out.println("KEY = D, VALUE =" + skipListMap.get("D"));
System.out.println("KEY = H, VALUE =" + skipListMap.get("H"));
/ / 2.2 traversal
skipListMap.forEach();
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
/ / 3. Delete
skipListMap.remove("B");
skipListMap.remove("C");
skipListMap.remove("G");
/ / 3.2 traversal
skipListMap.forEach();
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
}
Copy the codeThe test case output is as follows:
HeadIdx[level=3], Idx[null], Idx[null], Idx[null], Idx[null], Idx[key=E], Idx[null], Idx[key=G], Idx[null], Idx[null], Idx[null] HeadIdx[level=2], Idx[key=A], Idx[null], Idx[key=C], Idx[null], Idx[key=E], Idx[null], Idx[key=G], Idx[null], Idx[null], Idx[null] HeadIdx[level=1], Idx[key=A], Idx[null], Idx[key=C], Idx[null], Idx[key=E], Idx[null], Idx[key=G], Idx[null], Idx[null], Idx[null] HeadNode[BASE_HEADER], Node[key=A, value=1], Node[key=B, value=2], Node[key=C, value=3], Node[key=D, value=4], Node[key=E, value=5], Node[key=F, value=6], Node[key=G, value=7], Node[key=H, value=8], Node (key = I, value = 9), the Node [key = J, value = 10] -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the key = D, four key value = = H, VALUE=8 HeadIdx[level=3], Idx[null], Idx[null], Idx[null], Idx[null], Idx[key=E], Idx[null], Idx[key=G], Idx[null], Idx[null], Idx[null] HeadIdx[level=2], Idx[key=A], Idx[null], Idx[key=C], Idx[null], Idx[key=E], Idx[null], Idx[key=G], Idx[null], Idx[null], Idx[null] HeadIdx[level=1], Idx[key=A], Idx[null], Idx[key=C], Idx[null], Idx[key=E], Idx[null], Idx[key=G], Idx[null], Idx[null], Idx[null] HeadNode[BASE_HEADER], Node[key=A, value=1], Node[key=B, value=2], Node[key=C, value=3], Node[key=D, value=4], Node[key=E, value=5], Node[key=F, value=6], Node[key=G, value=7], Node[key=H, value=8], Node[key=I, value=9], Node[key=J, value=10] -------------------------------------------------- HeadIdx[level=3], Idx[null], Idx[null], Idx[key=E], Idx[null], Idx[null], Idx[null], Idx[null] HeadIdx[level=2], Idx[key=A], Idx[null], Idx[key=E], Idx[null], Idx[null], Idx[null], Idx[null] HeadIdx[level=1], Idx[key=A], Idx[null], Idx[key=E], Idx[null], Idx[null], Idx[null], Idx[null] HeadNode[BASE_HEADER], Node[key=A, value=1], Node[key=D, value=4], Node[key=E, value=5], Node[key=F, value=6], Node[key=H, value=8], Node[key=I, value=9], Node[key=J, value=10] --------------------------------------------------Copy the codeNote: the output of skip list is uncertain, I only show one of the output cases here, for reference only.
Finally, that’s the end of this article. If you have any questions about skip lists, please feel free to leave a comment below or email me privately. Thanks for watching!
PS: I never want to write a blog about data structure, mainly because drawing is too troublesome, 2333.