Life is the art of drawing without an eraser.Obstacles are those frightful things you see when you take your eyes off your goal. Life is the art of painting without an eraser. When you see too many difficulties, it’s usually when you lose sight of your goals.

This article mainly shares a very good dynamic data structure in all aspects – skip table. Realization is not the goal, the important thing is to understand its realization principle and thought, expand their own vision. All source code has been uploaded to Github: link

define

A skip list is a linked list of sequential elements that can be queried quickly. Although it is a linked list, but it sets the number of groups and lists with its advantages, the average search and insertion time complexity of the hop table is O(log n), better than the ordinary queue O(n), very efficient. Of course, there are pros and cons. Relatively speaking, it is very memory consuming (O(n)) because it creates multiple levels of indexes. Its search borrows from binary search. Use space for time, according to the random number to build multilevel index.

To sum up, skip list = linked list + multilevel index

For example,

For example, there is a linked list stored 1-100 positive integers, I want to quickly find 67, first establish a level index, take the middle value of 50, so that his level index is {1,50,100}, so that it can be determined that 67 between 50-100, but it is still not easy to find, so establish a second level index {1,25,50,75,100},, , and so on, constantly build indexes, narrow the search scope, can quickly locate.

Redis’s ordered collection also uses skip lists.

Why did Redis use a meter instead of a red-black tree?

Answer: First of all, Redis ordered set has insertion, deletion, search and iteration output ordered sequence these several operations, red black tree can also be completed, the time complexity is the same as the hop table. However, red-black trees are not as efficient as jumpers in finding data by interval. The code is easier to implement and more readable. It is not as complex as a red-black tree. It is more flexible, and it can effectively balance execution efficiency and memory consumption by changing the index building strategy.

implementation

Jump table structure

Here, default -1 data does not exist, maxLevel is level 0, forwards is multilevel index, and its toString method has been overridden for testing and viewing logs

    public class SNode {
        private int data = -1;
        private SNode[] forwards = new SNode[MAX_LEVEL];
        private int maxLevel = 0;

        @Override
        public String toString() {
            return "{data:" + data + ",level:" + maxLevel + "}"; }}Copy the code

This usage random level, mainly used to prevent pseudo-random, when the random odd number, level+1, through this method can almost achieve the purpose of uniform distribution.

    private int randomLevel() {
        int level = 1;
        for (int i = 1; i < MAX_LEVEL; i++) {
            if (random.nextInt() % 2 == 1) {
                ++level;
            }
        }
//        System.out.println("randomLevel-level = " + level);
        return level;
    }Copy the code

insert

The key to jump table is to insert, understand the implementation of the insert method, delete and search is a hundred.

The first loop is easier to understand, build the index

The second for loop, iterating in reverse order according to level, finds nodes in the multilevel index of the header list whose value is less than the inserted value and updates the multilevel index

The third for loop updates the multilevel index of the header list.

over

    private void insert(int data) {
        int level = randomLevel();
        SNode sNode = new SNode();
        sNode.data = data;
        sNode.maxLevel = level;
        SNode[] forwards = new SNode[level];
        for (int i = 0; i < level; i++) {
            forwards[i] = head;
        }
        SNode p = head;
        for (int i = level - 1; i >= 0; --i) {
            while(null ! = p.forwards[i] && p.forwards[i].data < data) { p = p.forwards[i]; } forwards[i] = p; }for (int i = 0; i < level; i++) {
            sNode.forwards[i] = forwards[i].forwards[i];
            forwards[i].forwards[i] = sNode;
        }
        if (levelCount < level)
            levelCount = level;
    }Copy the code

delete

The first deleted for loop has the same effect as the new for loop

The second loop is similar to the regular deletion of the linked list node.next = Node.next

    private void delete(int data) {
        SNode[] forwards = new SNode[levelCount];
        SNode sNode = head;
        for (int i = levelCount - 1; i >= 0; --i) {
            while(null ! = sNode.forwards[i] && sNode.forwards[i].data < data) { sNode = sNode.forwards[i]; } forwards[i] = sNode; }if(null ! = sNode.forwards[0] && sNode.forwards[0].data == data) {for (int i = levelCount - 1; i >= 0; --i) {
                if(null ! = forwards[i].forwards[i] && forwards[i].forwards[i].data == data) forwards[i].forwards[i] = forwards[i].forwards[i].forwards[i]; }}}Copy the code

To find the

The method is to traverse the multilevel index in reverse order, constantly narrow the scope, find the corresponding index level, and then find

Forwards [0]. Data == data

    private SNode findByValue(int data) {
        SNode sNode = head;
        for (int i = levelCount - 1; i >= 0; --i) {
            while (sNode.forwards[i] != null && sNode.forwards[i].data < data) {
                sNode = sNode.forwards[i];
            }
        }
        if(null ! = sNode.forwards[0] && sNode.forwards[0].data == data) {return sNode.forwards[0];
        }
        return null;
    }Copy the code

The test results



Based on the print, it looks something like this



The highest level is 8, and the highest level is 5.

end



Your likes and attention are the biggest support for me, thank you!