Documentation
¶
Overview ¶
Package skipList provide an implementation of skip list. But is not thread-safe in concurrency.
Index ¶
Constants ¶
const ( MAX_LEVEL = 32 PROBABILITY = 0.25 )
Comes from redis's implementation. Also you can see more detail in William Pugh's paper <Skip Lists: A Probabilistic Alternative to Balanced Trees>. The paper is in ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
Variables ¶
This section is empty.
Functions ¶
func Hash ¶
Hash will calculate the input's hash value using xxHash algorithm. It can be used to calculate the index of skip list. See more detail in https://cyan4973.github.io/xxHash/
Types ¶
type SkipList ¶
type SkipList struct {
// contains filtered or unexported fields
}
func NewSkipList ¶
NewSkipList will create and initialize a skip list with the given level. Level must between 1 to 32. If not, the level will set as 32. To determine the level, you can see the paper ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf. A simple way to determine the level is L(N) = log(1/PROBABILITY)(N). N is the count of the skip list which you can estimate. PROBABILITY is 0.25 in this case. For example, if you expect the skip list contains 10000000 elements, then N = 10000000, L(N) ≈ 12. After initialization, the head field's level equal to level parameter and point to tail field.
func (*SkipList) Delete ¶
Delete will find the index is existed or not firstly. If existed, delete it, otherwise do nothing.
func (*SkipList) ForEach ¶
ForEach will iterate the whole skip list and do the function f for each index and value. Function f will not modify the index and value in skip list. Don't Insert or Delete element in ForEach function.
func (*SkipList) Insert ¶
Insert will insert a node into skip list. If skip has these this index, overwrite the value, otherwise add it.
Source Files