How to realize Table hopping SkipList by python

This article introduces the relevant knowledge of "how to achieve jump table SkipList in python". 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!

Skip meter

Jump lists, also known as jump lists, add "jump" functions to ordered linked lists, released by William Pugh in 1990, and were originally designed to replace balanced trees (such as red-black trees).

Redis and LevelDB are both famous Key-Value databases, while SortedSet in Redis and MemTable in LevelDB all use jump tables.

Compared with the balanced tree, the implementation and maintenance of the jump table will be easier, and the average time complexity of searching, deleting and adding the jump table is O (logn).

The structure of the hopping table is shown in the figure:

It can be found that for a node Node, it contains multiple next pointers, and the next of different indexes represents the next node at different levels, and the next is the python definition of the node class Node:

Class Node (): def _ _ init__ (self,key,value,level): ": param level: the number of nexts layers corresponding to each node is different" self.key=key self.value=value self.nexts= [None] * level# node type next pointer The initial value is empty def _ str__ (self): # return "[key:" + str (self.key) + ", value:" + str (self.value) + "len:" + str (len (self.nexts)) + "]" return "[" + str (self.key) + "," + str (self.value) + "," + str (len (self.nexts)) + "]"

For more information about adding, deleting, and finding, see the complete code:

"" jump table Skip List Its original intention is to replace the red-black tree "" import randomimport mkl_randomimport timeclass SkipList (): def _ init__ (self): # head node does not store any data self.MAX_LEVEL = 32 # maximum number of level layers self.__first=SkipList.Node (None, None) Self.MAX_LEVEL) # actual number of level layers of self.__level=0# head node self.__p=0.25# is used to generate random level return class Node (): def _ _ init__ (self,key,value) when adding nodes Level): ": param level: the number of nexts layers corresponding to each node is different"self.key=key self.value=value self.nexts= [None] * level def _ str__ (self): # return" [key: "+ str (self.key) +" Value: "+ str (self.value) +" len: "+ str (len (self.nexts)) +"] "return" ["+ str (self.key) +", "+ str (self.value) +", "+ str (len (self.nexts)) +"] "def get (self Key): ": param key:: return: key corresponding to the value"self.keyCheck (key) node=self.__first for level in range (self.__level-1 Lindi 1): # find it on this layer The key whose key is greater than the node looks forward for while node.nexts [level] and node.nexts[ level] .key