This article focuses on the implementation. The first contact with the data structure of jump table was in Redis. At that time, I only learned the theoretical knowledge of jump table, which is difficult to support by theory alone. This can be realized when I was asked about jump table in the process of byte interview
Jump table is a very high-school data structure, which was invented by American scientist William Pugh. In a paper, he introduced the jump table data structure, insert, delete and other operations in great detail
basic thought
First of all, the skip list is an improvement of the ordered linked list. For the ordinary linked list, whether it is an ordinary linked list or an ordered linked list, the search operation of a node needs to be compared one by one from the head. The ordered nature of the ordered linked list is not available here. Is there any way to use the ordered nature of the ordered linked list to reduce the search time complexity of the ordered linked list?
Jump table is such a data structure. Based on the ordered linked list, jump table introduces the concept of layering. Each layer is an ordered linked list. Except for the lowest layer, other layers are indexes. Searching based on this index will be very fast, for example
For the structure in the figure above, if you want to find data 5, first start from the first layer. There is only one element in the first layer. Look down, 5 < 7 for the second time, and then look down. When you reach the third layer 4 < 5 < 7, look down from node 4. For the fourth layer, find data 5
At this point, we understand that this is actually the idea of dichotomy, so that the data can quickly approach the data to be found. This is the basic idea of jump table. Next, we will understand how to realize jump table, how to establish hierarchy, and how to insert and delete from the specific implementation
Data structure definition
First, you must define a node:
/**
* Implementation of hop table Node
* @param <T>
*/
class SkipNode<T>{
int key;
T value;
SkipNode right, down; //Represents the right and down pointers, respectively
public SkipNode(int key, T value) {
this.key = key;
this.value = value;
}
/**
* Initialization node is used to initialize the header node
* @param key
*/
public SkipNode(int key){
this.key = key;
this.value = null;
}
}
Then define a class
public class SkipList<T> {
SkipNode headNode; //Head node
int highLevel; //Level height
Random random; //The random value is used to judge whether to add a level later
final int MAX_LEVEL = 12; //Maximum layer series
/**
* Constructor initialization jump table
*/
public SkipList() {
this.random = new Random();
this.headNode = new SkipNode(Integer.MAX_VALUE);
highLevel = 0;
}
}
It should be noted that in order to make the head node the same as other nodes, we define a virtual head node here, and the element in it is integer MAX_ Value, there is also a random value of random, which will be used when inserting later. highLevel represents the level height of the current hop table, MAX_LEVEL represents the maximum number of layers
Search method
The process for finding methods is as follows:
1) Use temp as the header node, which will be used for traversal
2) If temp Key = = key, then the search is successful and the result is returned
3) If temp Right = = null, then the current level does not have this key, and must be down temp = temp down
4) If temp right != null && temp. Key < key, then continue to find temp = temp to the right right
5) If temp right != null && temp. Key > key, then the current level does not have this key, and you must look down for temp = temp down
/**
* Search method: four cases
* 1. If temp Key = = key, then the search is successful and the result is returned
* 2. If temp Right = = null, then the current level does not have this key, and must be down temp = temp down
* 3. If temp right != null && temp. Key < key, then continue to find temp = temp to the right right
* 4. If temp right != null && temp. Key > key, then the current level does not have this key, and you must look down for temp = temp down
*
* @param key
* @return
*/
public SkipNode search(int key) {
SkipNode temp = this.headNode;
while (temp != null) {
if (temp.key == key) {
return temp;
} else if (temp.right == null) {
temp = temp.down;
} else if (temp.key < key) {
temp = temp.right;
} else {
temp = temp.down;
}
}
return null;
}
Delete method
The process of deleting the method is:
1) If temp Right = = null, then temp = temp down
2) If temp right != null && temp.right. Key = key, then delete temp Right node, and then delete the next level node temp = temp down
3) If temp right != null && temp. right. Key < key, then temp = temp right
4) If temp right != null && temp. right. Key > key, then the current level does not have this key, temp = temp down
/**
* Delete: find the previous node to delete, and then delete it. There are four cases:
* 1. If temp Right = = null, then temp = temp down
* 2. If temp right != null && temp.right. Key = key, then delete temp Right node, and then delete the next level node temp = temp down
* 3. If temp right != null && temp. right. Key < key, then temp = temp right
* 4. If temp right != null && temp. right. Key > key, then the current level does not have this key, temp = temp down
*
* @param key
*/
public void delete(int key) {
SkipNode temp = this.headNode;
while (temp != null) {
if (temp.right == null) {
temp = temp.down;
} else if (temp.right.key == key) {
temp.right = temp.right.right; //Delete node
temp = temp.down; //Then look down
} else if (temp.right.key < key) {
temp = temp.right;
} else {
temp = temp.down;
}
}
}
Insertion method
/**
* There are three issues to consider when inserting:
* 1. This node must be inserted at the bottom layer, but does the upper layer need to be inserted? The random value method is used to determine whether to insert this node to the upper layer
* 2. If the highest level needs to create a new higher level, what should I do? You need to create a new Node as the new head Node and point to the old head Node at the same time
* 3. How to find the nodes to be inserted in the upper layer? If there is a two-way pointer, it is simple, but how does a one-way pointer operate? With the help of the stack, the current node is stored in the stack every time it goes down, and can be taken out the next time it needs to be inserted
*
* @param node
*/
public void add(SkipNode<T> node) {
int key = node.key;
//Determine whether the node exists
SkipNode findNode = this.search(node.key);
if (findNode != null) {
findNode.value = node.value;
return;
}
Stack<SkipNode> stack = new Stack<>();
SkipNode temp = this.headNode;
while (temp != null) {
if (temp.right == null || temp.right.key > key) {
stack.add(temp);
temp = temp.down;
} else {
temp = temp.right;
}
}
int level = 1; //Represents the current number of layers
SkipNode downNode = null; //Vertical precursor node
while (!stack.isEmpty()) {
temp = stack.pop(); //Points to be inserted backward
SkipNode nodeTemp = new SkipNode(node.key, node.value);
nodeTemp.down = downNode;
downNode = nodeTemp; //Process horizontal direction
//null description on the right is inserted at the end
if (temp.right == null) {
temp.right = nodeTemp;
} else {
nodeTemp = temp.right;
temp.right = nodeTemp;
}
//Consider whether you need to insert up
if (level > this.MAX_LEVEL) break;
if (this.random.nextDouble() > 0.5) break; //Luck doesn't need to be inserted
level++;
if (level > this.highLevel) {
highLevel = level;
//Create a new header node
SkipNode headNew = new SkipNode(Integer.MAX_VALUE);
headNew.down = this.headNode;
this.headNode = headNew;
stack.add(headNew);
}
}
}
Printing method
public void print() {
SkipNode teamNode = headNode;
int index = 1;
SkipNode last = teamNode;
while (last.down != null) {
last = last.down;
}
while (teamNode != null) {
SkipNode enumNode = teamNode.right;
SkipNode enumLast = last.right;
System.out.printf("%-8s", "head->");
while (enumLast != null && enumNode != null) {
if (enumLast.key == enumNode.key) {
System.out.printf("%-5s", enumLast.key + "->");
enumLast = enumLast.right;
enumNode = enumNode.right;
} else {
enumLast = enumLast.right;
System.out.printf("%-5s", "");
}
}
teamNode = teamNode.down;
index++;
System.out.println();
}
}
main
public static void main(String[] args) {
SkipList<Integer> list = new SkipList<Integer>();
for (int i = 1; i < 20; i++) {
list.add(new SkipNode(i, 666));
}
System.out.println("Before deletion");
list.print();
list.delete(4);
list.delete(8);
System.out.println("After deletion");
list.print();
}
Complete code
package cn.noteblogs.skipList;
import com.sun.jmx.snmp.SnmpOid;
import java.awt.*;
import java.util.Random;
import java.util.Stack;
/**
* Implementation of hop table Node
* @param <T>
*/
class SkipNode<T>{
int key;
T value;
SkipNode right, down; //Represents the right and down pointers, respectively
public SkipNode(int key, T value) {
this.key = key;
this.value = value;
}
/**
* Initialization node is used to initialize the header node
* @param key
*/
public SkipNode(int key){
this.key = key;
this.value = null;
}
}
/**
* Skip table
*/
public class SkipList<T> {
SkipNode headNode; //Head node
int highLevel; //Level height
Random random; //The random value is used to judge whether to add a level later
final int MAX_LEVEL = 12; //Maximum layer series
/**
* Constructor initialization jump table
*/
public SkipList() {
this.random = new Random();
this.headNode = new SkipNode(Integer.MAX_VALUE);
highLevel = 0;
}
/**
* Search method: four cases
* 1. If temp Key = = key, then the search is successful and the result is returned
* 2. If temp Right = = null, then the current level does not have this key, and must be down temp = temp down
* 3. If temp right != null && temp. Key < key, then continue to find temp = temp to the right right
* 4. If temp right != null && temp. Key > key, then the current level does not have this key, and you must look down for temp = temp down
*
* @param key
* @return
*/
public SkipNode search(int key) {
SkipNode temp = this.headNode;
while (temp != null) {
if (temp.key == key) {
return temp;
} else if (temp.right == null) {
temp = temp.down;
} else if (temp.key < key) {
temp = temp.right;
} else {
temp = temp.down;
}
}
return null;
}
/**
* Delete: find the previous node to delete, and then delete it. There are four cases:
* 1. If temp Right = = null, then temp = temp down
* 2. If temp right != null && temp.right. Key = key, then delete temp Right node, and then delete the next level node temp = temp down
* 3. If temp right != null && temp. right. Key < key, then temp = temp right
* 4. If temp right != null && temp. right. Key > key, then the current level does not have this key, temp = temp down
*
* @param key
*/
public void delete(int key) {
SkipNode temp = this.headNode;
while (temp != null) {
if (temp.right == null) {
temp = temp.down;
} else if (temp.right.key == key) {
temp.right = temp.right.right; //Delete node
temp = temp.down; //Then look down
} else if (temp.right.key < key) {
temp = temp.right;
} else {
temp = temp.down;
}
}
}
/**
* There are three issues to consider when inserting:
* 1. This node must be inserted at the bottom layer, but does the upper layer need to be inserted? The random value method is used to determine whether to insert this node to the upper layer
* 2. If the highest level needs to create a new higher level, what should I do? You need to create a new Node as the new head Node and point to the old head Node at the same time
* 3. How to find the nodes to be inserted in the upper layer? If there is a two-way pointer, it is simple, but how does a one-way pointer operate? With the help of the stack, the current node is stored in the stack every time it goes down, and can be taken out the next time it needs to be inserted
*
* @param node
*/
public void add(SkipNode<T> node) {
int key = node.key;
//Determine whether the node exists
SkipNode findNode = this.search(node.key);
if (findNode != null) {
findNode.value = node.value;
return;
}
Stack<SkipNode> stack = new Stack<>();
SkipNode temp = this.headNode;
while (temp != null) {
if (temp.right == null || temp.right.key > key) {
stack.add(temp);
temp = temp.down;
} else {
temp = temp.right;
}
}
int level = 1; //Represents the current number of layers
SkipNode downNode = null; //Vertical precursor node
while (!stack.isEmpty()) {
temp = stack.pop(); //Points to be inserted backward
SkipNode nodeTemp = new SkipNode(node.key, node.value);
nodeTemp.down = downNode;
downNode = nodeTemp; //Process horizontal direction
//null description on the right is inserted at the end
if (temp.right == null) {
temp.right = nodeTemp;
} else {
nodeTemp = temp.right;
temp.right = nodeTemp;
}
//Consider whether you need to insert up
if (level > this.MAX_LEVEL) break;
if (this.random.nextDouble() > 0.5) break; //Luck doesn't need to be inserted
level++;
if (level > this.highLevel) {
highLevel = level;
//Create a new header node
SkipNode headNew = new SkipNode(Integer.MAX_VALUE);
headNew.down = this.headNode;
this.headNode = headNew;
stack.add(headNew);
}
}
}
public void print() {
SkipNode teamNode = headNode;
int index = 1;
SkipNode last = teamNode;
while (last.down != null) {
last = last.down;
}
while (teamNode != null) {
SkipNode enumNode = teamNode.right;
SkipNode enumLast = last.right;
System.out.printf("%-8s", "head->");
while (enumLast != null && enumNode != null) {
if (enumLast.key == enumNode.key) {
System.out.printf("%-5s", enumLast.key + "->");
enumLast = enumLast.right;
enumNode = enumNode.right;
} else {
enumLast = enumLast.right;
System.out.printf("%-5s", "");
}
}
teamNode = teamNode.down;
index++;
System.out.println();
}
}
public static void main(String[] args) {
SkipList<Integer> list = new SkipList<Integer>();
for (int i = 1; i < 20; i++) {
list.add(new SkipNode(i, 666));
}
System.out.println("Before deletion");
list.print();
list.delete(4);
list.delete(8);
System.out.println("After deletion");
list.print();
}
}
