Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to design and implement jump table SkipList". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Quickly understand the jump table

The jump table (jump table for short) was invented by American computer scientist William Pugh in 1989. In his paper "Skip lists: a probabilistic alternative to balanced trees", he introduces in detail the data structure of the jump table and the operations such as inserting and deleting.

Jump table (SkipList, full name jump table) is a data structure used for rapid search of ordered element sequences. Jump table is a randomized data structure, which is essentially an ordered linked list that can be searched in two parts. The skip table adds a multi-level index to the original ordered linked list to achieve fast search through the index. Jump tables can not only improve search performance, but also improve the performance of insert and delete operations. It is comparable to the red-black tree and the AVL tree in performance, but the principle of the jump table is very simple and the implementation is much simpler than the red-black tree.

You can see some keywords here: linked list (ordered linked list), index, binary search. You must have a first impression in your mind, but you may still not know how diao this "hopping linked list" is, and you may even wonder: what does it have to do with following mechanization? You will soon get the answer below!

Looking back at linked lists, we know that linked lists and sequential lists (arrays) usually fall in love with each other, appear in pairs, each has its own advantages and disadvantages. The advantage of linked lists is more efficient insertion and deletion. The pain point is that the query is very slow! Each query is an O (n) complex operation, and the linked list probably makes itself want to cry.

This is a linked list of leading nodes (the header node is equivalent to a fixed entry and does not store meaningful values). Each search needs to be enumerated one by one, which is quite slow. Can we optimize it a little bit to make it jump a little bit? The answer is yes. We know that many algorithms and data structures trade space for time. We add an index on it so that some nodes can be located directly at the upper level, so that the query time of the linked list is nearly halved. Although the linked list itself is not happy, but put away its face that wants to cry.

In this way, when querying a node, we will first quickly locate the range of the node from the upper level, and if we find the specific scope down and then the search cost is very low, of course, a downward index (pointer) will be added to the structural design of the table to find and determine the underlying node. The average search speed is O (nmax 2). But when the number of nodes is large, it is still very slow. We all know that binary search can be folded in half every time to compress the search range, and it would be perfect if ordered linked lists could jump in the same way. It is true that a jump table can give a linked list a data structure that is close to the efficiency of binary lookup, and its principle is to add several layers of indexes to it to optimize the search speed.

As you can see from the above figure, the performance of searching an ordered linked list through such a data structure is close to dichotomy. It is to maintain so many layers of index above, first look for the last location on the top-level index that is less than the current lookup element, and then skip to the sub-high-level index to continue searching until it jumps to the lowest level. at this time and very close to the location of the element to be found (if the lookup element exists). Because you can skip more than one element at a time according to the index, the lookup speed of the skip search becomes faster.

For an ideal jump table, the number of index nodes in each upward layer is 1 / 2 of that in the next layer. So if n nodes increase the number of nodes (1 beat 2 nodes 1 move 4 + …) Does the structure really exist? High probability does not exist, because as a linked list, it is necessary to add and delete some operations that should be checked. Deletions and inserts may change the whole structure, so the above structures are ideal, and whether to add upper-level indexes at insert time is a matter of probability (1 >

The addition, deletion, modification and query of the jump watch

The above has a little understanding of what the jump table is, so here we will talk about the addition, deletion, modification and search process of the jump table. In the process of implementing this jump table, in order to facilitate the operation, we set the key of the head node (head) of the jump table to the minimum value of int (must satisfy the small left and right for easy comparison).

For each node setting, set to the SkipNode class, in order to prevent beginners from confusing the next down or right, directly set the right,down two pointers.

Class SkipNode {int key; T value; SkipNode right,down;// pointer in the lower right direction public SkipNode (int key,T value) {this.key=key; this.value=value;}}

The structure and initialization of the jump table are also important. The main parameters and initialization methods are:

Public class SkipList {SkipNode headNode;// header node, entry int highLevel;// current jump table index number of layers Random random;// is used to toss a coin final int MAX_LEVEL = 32 Integer.MIN_VALUE,null / maximum layer SkipList () {random=new Random (); headNode=new SkipNode (Integer.MIN_VALUE,null); highLevel=0;} / / other methods}

Query operation

In many cases, linked lists may be connected in this way just to an element or key as a standard for ordering. So it's possible that there is some value inside the linked list. However, modification and query are actually one operation to find the key number (key). And the process of finding is simple, setting up a temporary node team=head. When team is not null, the process is roughly as follows:

(1) starting from the team node, if the key of the current node is equal to the key of the query, then the current node is returned (if it is a modification operation, then the value can be modified all the way down).

(2) if the key is not equal and the right side is null, then the proof can only go down (the result may appear in the lower right direction), and then team=team.down

(3) if the key is not equal, the right side is not null, and the right node key is less than the key to be queried. Then it means that the sibling can also turn to the right, and at this time team=team.right

(4) (otherwise) if the key is not equal, the right side is not null, and the right node key is greater than the key to be queried. Then it means that if there is a result, it is between this index and the next index, at this time team=team.down.

Eventually, you will follow this step to return the correct node or null (indicating that it is not found).

For example, when querying 12 nodes in the figure above, the first step is to start from head and find that the right side is not empty and 7MAX_LEVEL) / / has reached the highest node break; double num=random.nextDouble (); / / [0-1] random number if (num > 0.5) / / unlucky end break; level++ If (level > highLevel) / / higher than the current maximum height but still within the allowable range need to change the head node {highLevel=level; / / need to create a new node SkipNode highHeadNode=new SkipNode (Integer.MIN_VALUE, null); highHeadNode.down=headNode; headNode=highHeadNode;// change head stack.add (headNode) / / next time throw out head} "how to design and implement jump table SkipList" content will be introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.