Pay attention to the public account, communicate together, wechat search: sneak forward
What is a skip list
The balanced data structures often used in development are B number, red and black number, and AVL number. But if you’re asked to implement one of these, it’s hard, it takes time to implement. The skip list is a fast search data structure based on linked list array, which is used by open source software Redis and LevelDB. It is as efficient as red-black trees and AVL trees
Skip list structure
structure
public class SkipList<T> {
// Start and end of skip lists
private SkipListNode<T> head;
// The length of the element in the skip list
private int length;
// The historical maximum number of hops
public int maxLevel;
public SecureRandom random;
private static final int MAX_LEVEL = 31;
public SkipList(a) {
// Initializes the head and tail nodes and their relationship
head = new SkipListNode<>(SkipListNode.HEAD_SCORE, null, MAX_LEVEL);
// Initialize the size, layer, random
length = 0;
maxLevel = 0; // The number of layers is calculated from zero
random = newSecureRandom(); }...Copy the code- Header: Points to the head node of the skip list
- MaxLevel: Records the number of layers of the current skip table with the maximum number of layers
- Length: The length of the element in the list
node
Skip list node composition: front node, back node, point value (map key value), and storage object value
public class SkipListNode<T> {
// Sort the score values in the hop table
public double score;
public T value;
public int level;
// Front and rear nodes
public SkipListNode<T> next,pre;
// The layer formed by the 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 skiplistNodes and each layer of nodes
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(a) { return "Node[score=" + score + ", value=" + value + "]"; }}Copy the codeA jumper trades space for time
- The skip list node I implemented includes a levelNode member property. It is the node layer. Skip lists are key to fast access
- Usually, we access an array in order to traverse, while the efficiency of skip list is higher than that of array list, because it uses node layer to store multi-level index, forming a sparse index, so it needs more memory space
How fast skip lists are
- If a linked list has N nodes and one node is extracted from every two nodes to create an index, then the number of nodes in the first index is about N /2, the number of nodes in the second index is about N /4, and so on, the number of nodes in the m index is about N /(2^m).
- Data can be queried from the m-layer index to the m-1 layer index. And m minus one is about 1/2 of m. In other words, the optimal time complexity is order log over N.
- Worst-case scenario. In practice, each level of index cannot be implemented one level at a time with the amount of data folded in half. So in a compromise, the index for each layer is created randomly with the full amount of data. That is, the worst-case time complexity is O(N), but the optimal time complexity is the same
The query
- The query starts by traversing index M at the highest maxLevel. Follow these steps to find the left node equal to score or closest to score
- 1: If the score of the next node in the same index is less than the query score, jump to the next node. cur = next
- 2: If next is empty. Or the next node score is greater than the query score. Then jump to the next level m-1 index, loop 2
- Repeat steps 1 and 2 until the access node score matches the query score, or the index level is zero
// SkipList
private SkipListNode<T> findNearestNode(double score) {
int curLevel = maxLevel;
SkipListNode<T> cur = head.levelNode[curLevel];
SkipListNode<T> next = cur.next;
// Have the same score as the current node or next is null
while(score ! = cur.score && curLevel >0) {
// 1 to the right next traversal
if(next ! =null && score >= next.levelNode[0].score) {
cur = next;
}
next = cur.levelNode[curLevel].next;
// 2 traverses down, the number of layers is reduced by 1
while ((next == null || score < next.levelNode[0].score) && curLevel > 0) { next = cur.levelNode[--curLevel].next; }}// The lowest node.
return cur.levelNode[0];
}
public SkipListNode<T> get(double score) {
// Returns the node at the bottom of the hop table that is closest to this score
SkipListNode<T> p = findNearestNode(score);
// Score is the same, return this node
return p.score == score ? p : null;
}
Copy the codeinsert
- Replace value if the score exists
- If the node corresponding to the score does not exist, a random number of index layers is level (the value ranges from 0 to 31). Then add the index from level 0 to level based on the node property levelNode
//SkipList
public T put(double score, T value) {
// Get the node closest to the key at the bottom of the hop table
SkipListNode<T> p = findNearestNode(score);
if (p.score == score) {
// In a hop table, only the lowest node has a real value. You only need to change the lowest value
T old = p.value;
p.value = value;
return old;
}
// nowNode is the lowest level of newly created 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;
}
// The loop starts when p has more layers than nowNode
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 for Pre
if(pre.next ! =null) {
pre.next.pre = now;
}
// Finally consider pre
pre.next = now;
}
Copy the codedelete
- Use the get method to find the element and then unreference the node attribute levelNode before and after each level of index
//SkipList
public T remove(double score){
// Find the underlying node for this key
SkipListNode<T> now = get(score);
if (now == null) {
return null;
}
SkipListNode<T> curNode, next;
// Unreference the node attribute levelNode before and after each level 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 to return the old value
return now.value;
}
Copy the codeUse the sample
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();
}
Copy the codeCorrections are welcome
Refer to the article
- Redis design and implementation
- Summary of skip tables (skipList) – Java edition
- Data structures and algorithms — skip tables