Pay attention to the official account and exchange with each other. Search by WeChat: Sneak ahead.
What is a jump list
The balance data structures often used in development include B number, red black number and AVL number. But if you implement one of them, it is very difficult and takes time to implement. The jump linked list is a fast search data structure based on the linked list array. At present, it is used by the open source software Redis and LevelDB. Its efficiency is comparable to that of red black tree and AVL tree
Jump linked list structure
structure
public class SkipList<T> {
//Head and tail of jump table
private SkipListNode<T> head;
//The length of the elements contained in the jump table
private int length;
//The historical maximum number of layers of the skip table
public int maxLevel;
public SecureRandom random;
private static final int MAX_LEVEL = 31;
public SkipList() {
//Initialize the head and tail nodes and their relationship
head = new SkipListNode<>(SkipListNode.HEAD_SCORE, null, MAX_LEVEL);
//Initialization size, layer, random
length = 0;
maxLevel = 0; // The number of layers is calculated from zero
random = new SecureRandom();
}
...
- Header: points to the header node of the jump table
- maxLevel: records the layers of the node with the largest number of layers in the current hop table
- Length: the length of the elements in the linked list
node
The composition of the jump linked list node: the front node, the back node, the score (the key value of the map), and the storage object value
public class SkipListNode<T> {
//Score value sorted in the skip table
public double score;
public T value;
public int level;
// Front and rear nodes
public SkipListNode<T> next,pre;
//Layer formed by upper and lower nodes
public SkipListNode<T>[] levelNode;
private SkipListNode(double score, int level){
this.score = score;
this.level = level;
}
public SkipListNode(double score, T value, int level) {
this.score = score;
this.value = value;
this.level = level;
this.levelNode = new SkipListNode[level+1];
//Initialize SkipListNode and node of each layer
for (int i = level; i > 0; --i) {
levelNode[i] = new SkipListNode<T>(score, level);
levelNode[i].levelNode = levelNode;
}
this.levelNode[0] = this;
}
@Override
public String toString() { return "Node[score=" + score + ", value=" + value + "]"; }
}
Jump table is to trade space for time
- The jump linked list node I implemented includes a levelNode member attribute. It is the node layer. The key point of fast access to jump linked list is it
- We usually access an array in order, and the efficiency of jump linked list is higher than that of array linked list, because it uses node layer to store multi-level indexes to form a sparse index, so it needs more memory space
How fast is the jump list
- If a linked list has n nodes and one node is extracted from every two nodes to establish an index, the number of nodes of the first layer index is about n/2, the number of nodes of the second layer index is about n/4, and so on. The number of nodes of the m-layer index is about n/(2^m)
- When accessing data, you can locate the m-1 layer index data from the m-layer index query. m-1 is about 1 / 2 of m layer. That is, the optimal time complexity is O(log/N)
- Worst case scenario. In the actual implementation, each layer of index cannot be halved by the amount of data each time. Therefore, in a compromise way, the index of each layer is randomly built with full data. In other words, the worst-case time complexity is O(N), but the optimal time complexity remains unchanged
query
- The query starts by traversing the index m of the highest maxLevel. Follow the steps below to find the left node equal to or closest to score
- 1: If the next node score of the same layer index is less than the query score, skip to the next node. cur = next
- 2: If next is empty. Or the score of the next node is greater than the query score. Then skip to the next layer m-1 index and cycle 2
- Cycle steps 1 and 2 until the access node score is consistent with the query score, or the index layer is zero
// SkipList
private SkipListNode<T> findNearestNode(double score) {
int curLevel = maxLevel;
SkipListNode<T> cur = head.levelNode[curLevel];
SkipListNode<T> next = cur.next;
// The score is the same as the current node or next is null
while (score != cur.score && curLevel > 0) {
// 1 right next traversal
if (next != null && score >= next.levelNode[0].score) {
cur = next;
}
next = cur.levelNode[curLevel].next;
// 2. Traverse down and reduce the number of layers by 1
while ((next == null || score < next.levelNode[0].score) && curLevel > 0) {
next = cur.levelNode[--curLevel].next;
}
}
// The bottom node.
return cur.levelNode[0];
}
public SkipListNode<T> get(double score) {
//Returns the node closest to the score at the bottom of the jump table
SkipListNode<T> p = findNearestNode(score);
//If the score is the same, this node is returned
return p.score == score ? p : null;
}
insert
- If the score exists, replace value
- If the node corresponding to the score does not exist, a random index level (value 0 ~ 31) is selected. Then add 0 to the index of the level layer by relying on the node attribute levelNode
//SkipList
public T put(double score, T value) {
//First, get the node closest to the key at the bottom of the hop table
SkipListNode<T> p = findNearestNode(score);
if (p.score == score) {
// In the jump table, only the bottom node has a real value. Just modify the bottom value
T old = p.value;
p.value = value;
return old;
}
// nowNode is the newly created bottom node. Index levels 0 to 31
int nodeLevel = (int) Math.round(random.nextDouble() * 32);
SkipListNode<T> nowNode = new SkipListNode<T>(score, value, nodeLevel);
//Initialize each layer and connect the nodes before and after each layer
int level = 0;
while (nodeLevel >= p.level) {
for (; level <= p.level; level++) {
insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]);
}
p = p.pre;
}
// At this time, the number of layers of p is greater than that of nowNode before entering the cycle
for (; level <= nodeLevel; level++) {
insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]);
}
this.length ++ ;
if (this.maxLevel < nodeLevel) {
maxLevel = nodeLevel;
}
return value;
}
private void insertNodeHorizontally(SkipListNode<T> pre, SkipListNode<T> now) {
//Consider now first
now.next = pre.next;
now.pre = pre;
//Consider the next node of pre
if (pre.next != null) {
pre.next.pre = now;
}
//Finally, consider pre
pre.next = now;
}
delete
- Use the get method to find the element, and then release the reference relationship between the node attribute levelNode and the index of each layer
//SkipList
public T remove(double score){
//Find the node corresponding to this key at the bottom
SkipListNode<T> now = get(score);
if (now == null) {
return null;
}
SkipListNode<T> curNode, next;
//Dereference the node attribute levelNode before and after each layer index
for (int i = 0; i <= now.level; i++){
curNode = now.levelNode[i];
next = curNode.next;
if (next != null) {
next.pre = curNode.pre;
}
curNode.pre.next = curNode.next;
}
this.length--; //Update size and return the old value
return now.value;
}
Use example
public static void main(String[] args) {
SkipList<String> list=new SkipList<>();
list.printSkipList();
list.put(1, "csc");
list.printSkipList();
list.put(3, "lwl");
list.printSkipList();
list.put(2, "hello world!");
list.printSkipList();
System.out.println(list.get(2));
System.out.println(list.get(4));
list.remove(2);
list.printSkipList();
}
Welcome refers to an error in the text
Reference articles
- Design and implementation of redis
- Skip list (skip list) Summary - java version
- Data structure and algorithm -- jump table