I want to introduce jump watch to you naturally .

think , We

1） Search for a number in an ordered sequence

2） Or insert a number in the right place

How to do it ?

Is it simple

For the first operation , We can compare one by one , In an array, we can divide it into two parts , It's faster than a linked list

For the second operation , There's no use in two , Because to find the position, we have to move the position one by one in the array , The time complexity is still o(n).

So how can we invent a structure that can search and insert faster ?

You can put some marks on it ：

So we connect the markers , When searching for a number, start with the tag. If the next tag is larger than itself, go down , Because it's not going to meet the requirements .

For example, we need to search 18：

Because it can span many numbers at a time , Naturally, it's faster .

Since you can mark it , We can improve it , Choose some numbers and mark them again ：

So we search 20 That's true ：

In the end, we can mark many layers , We start at the top , You can skip a lot of numbers at a time （ It's still on the right. When it's big, go down ）.

For example, search 26：

Best case scenario , That is, the marks on each layer are reduced by half , So you get to the top and search down , In fact, it's no different from two points , We linked the bottom with a list , Inserting an element does not require moving the element , The so-called watch skipping is more than half done .

Now the problem is , We have a new number , How many layers should it be marked ?

（ At first, there was not a single number , So it solved the problem , We can always update it with this strategy ）

I was a little surprised , I thought there would be some very strong mathematical algorithms , Can guarantee a very good search efficiency , I think too much .

We have a new number , There's half the probability of a mark , There's a half chance you can't play .

For a number with a layer of marks , We are still this way , It has a half chance of marking up again , Cycle in turn .

So the probability of reaching each layer is less than half .

The number of nodes in each layer can be maintained in good efficiency （ The most perfect is to achieve a two-point effect ）

Analyze it again , In fact, for the same number ：

wait ..

There's no need to use pointers all the time , Because we know , Finding a number through a pointer is much slower than subscript .

So all the marks of the same number , There's no need to use a pointer , Low efficiency, not easy to maintain , Use one list Save it .

such , We design a structure of all the marks of a number ：
public static class SkipListNode { public Integer value;// Value of itself public
ArrayList<SkipListNode> nextNodes; // An array of nodes pointing to the next element , The length depends on the face . public
SkipListNode(Integer value) { this.value = value; nextNodes = new
ArrayList<SkipListNode>(); } }
take integer Compare the operation of encapsulation ：
private boolean lessThan(Integer a, Integer b) { return a.compareTo(b) < 0; }
private boolean equalTo(Integer a, Integer b) { return a.compareTo(b) == 0; }
Find the node that should turn down in this layer ：
// Returns the node at a given level with highest value less than e private
SkipListNode findNext(Integer e, SkipListNode current, int level) {
SkipListNode next = current.nextNodes.get(level); while (next != null) {
Integer value = next.value; if (lessThan(e, value)) { // e < value break; }
current = next; next = current.nextNodes.get(level); } return current; }
In this way, we can write down a method to find them layer by layer , And packaged into find(Integer e) The form of ：
// Returns the skiplist node with greatest value <= e private SkipListNode
find(Integer e) { return find(e, head, maxLevel); } // Returns the skiplist
node with greatest value <= e // Starts at node start and level private
SkipListNode find(Integer e, SkipListNode current, int level) { do { current =
findNext(e, current, level); } while (level-- > 0); return current; }
The method just now is to find the maximum value less than or equal to the target , If the value found is equal to the target , This target exists in the skip table . Otherwise it doesn't exist .
public boolean contains(Integer value) { SkipListNode node = find(value);
return node != null && node.value != null && equalTo(node.value, value); }
Now we can add a new point , Pay attention to the marking of each layer ：
public void add(Integer newValue) { if (!contains(newValue)) { size++; int
level = 0; while (Math.random() < PROBABILITY) { level++;// How many layers can you see } while
(level > maxLevel) {// Greater than the current maximum number of layers head.nextNodes.add(null);// Direct connect system maximum maxLevel++; }
SkipListNode newNode = new SkipListNode(newValue); SkipListNode current =
head;// Previous node , That is to say, the goal should be inserted current after do {// Each layer can be marked before it goes down , It is to insert a new node into the linked list current =
current.nextNodes.get(level)); current.nextNodes.set(level, newNode); } while
(level-- > 0); } }
The same is true of deletion
public void delete(Integer deleteValue) { if (contains(deleteValue)) {
SkipListNode deleteNode = find(deleteValue); size--; int level = maxLevel;
SkipListNode current = head; do {// It is an operation of deleting nodes in a linked list current =
findNext(deleteNode.value, current, level); if (deleteNode.nextNodes.size() >
level) { current.nextNodes.set(level, deleteNode.nextNodes.get(level)); } }
while (level-- > 0); } }
As a container ,Iterator Is that necessary , There must be something in it hasNext and next bar ?
public static class SkipListIterator implements Iterator<Integer> { SkipList
list; SkipListNode current; public SkipListIterator(SkipList list) { this.list
= list; this.current = list.getHead(); } public boolean hasNext() { return
current.nextNodes.get(0) != null; } public Integer next() { current =
current.nextNodes.get(0); return current.value; } }
We're done with this watch skipping .

What about real work , We don't normally let it go to infinite levels , If there is a number, its popularity explosion, random number rush to 10000 layers ?

So it includes redis Some hop table implementation in , There is a maximum number of layers .

There seems to be nothing else .

Finally, post all the codes .
import java.util.ArrayList; import java.util.Iterator; public SkipListDemo {
public static class SkipListNode { public Integer value; public
ArrayList<SkipListNode> nextNodes; public SkipListNode(Integer value) {
this.value = value; nextNodes = new ArrayList<SkipListNode>(); } } public
static class SkipListIterator implements Iterator<Integer> { SkipList list;
SkipListNode current; public SkipListIterator(SkipList list) { this.list =
list; this.current = list.getHead(); } public boolean hasNext() { return
current.nextNodes.get(0) != null; } public Integer next() { current =
current.nextNodes.get(0); return current.value; } } public static class
SkipList { private SkipListNode head; private int maxLevel; private int size;
private static final double PROBABILITY = 0.5; public SkipList() { size = 0;
(!contains(newValue)) { size++; int level = 0; while (Math.random() <
maxLevel++; } SkipListNode newNode = new SkipListNode(newValue); SkipListNode
current = head; do { current = findNext(newValue, current, level);
current.nextNodes.set(level, newNode); } while (level-- > 0); } } public void
delete(Integer deleteValue) { if (contains(deleteValue)) { SkipListNode
deleteNode = find(deleteValue); size--; int level = maxLevel; SkipListNode
current = head; do { current = findNext(deleteNode.value, current, level); if
(deleteNode.nextNodes.size() > level) { current.nextNodes.set(level,
deleteNode.nextNodes.get(level)); } } while (level-- > 0); } } // Returns the
skiplist node with greatest value <= e private SkipListNode find(Integer e) {
return find(e, head, maxLevel); } // Returns the skiplist node with greatest
value <= e // Starts at node start and level private SkipListNode find(Integer
e, SkipListNode current, int level) { do { current = findNext(e, current,
level); } while (level-- > 0); return current; } // Returns the node at a given
level with highest value less than e private SkipListNode findNext(Integer e,
SkipListNode current, int level) { SkipListNode next =
current.nextNodes.get(level); while (next != null) { Integer value =
next.value; if (lessThan(e, value)) { // e < value break; } current = next;
next = current.nextNodes.get(level); } return current; } public int size() {
return size; } public boolean contains(Integer value) { SkipListNode node =
find(value); return node != null && node.value != null && equalTo(node.value,
value); } public Iterator<Integer> iterator() { return new
SkipListIterator(this); }
/******************************************************************************
* Utility Functions *
******************************************************************************/
private boolean lessThan(Integer a, Integer b) { return a.compareTo(b) < 0; }
private boolean equalTo(Integer a, Integer b) { return a.compareTo(b) == 0; } }
public static void main(String[] args) { } }

Technology
Daily Recommendation
views 4
views 3