详解全网最快Go泛型跳表【内附源码】

// 对于Key可以用 < 和 == 运算符比较的类型，调这个函数来创建
func NewSkipList[K Ordered, V any]() *SkipList[K, V]
// 其他情况，需要自定义Key类型的比较函数
func NewSkipListFunc[K any, V any](keyCmp CompareFn[K]) *SkipList[K, V]

// 从一个map来构建，仅为方便写Literal，go没法对自定义类型使用初始化列表。
func NewSkipListFromMap[K Ordered, V any](m map[K]V) *SkipList[K, V]

IsEmpty() bool // 表是否为空
Len() int // 返回表中元素的个数
Clear() // 清空跳表
Has(K) bool // 检查跳表中是否存在指定的key
Find(K) *V // Finds element with specific key.
Insert(K, V) // Inserts a key-value pair in to the container or replace existing value.
Remove(K) bool // Remove element with specific key.

type skipListNode[K any, V any] struct {
    key K
    value V
    // 指向下一个节点的指针的数组，不同深度的节点长度不同，[0]表示最下层
    next []*skipListNode[K, V]
}

func randomLevel() int {
    level := 0
    for math.Float64() < 0.5 {
        level++
    }
    return level
}

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

func (sl *Skiplist) randomLevel() int {
    total := uint64(1)<<uint64(sl.maxLevel) - 1 // 2^n-1
    k := sl.rander.Uint64() % total
    levelN := uint64(1) << (uint64(sl.maxLevel) - 1)

    level := 1
    for total -= levelN; total > k; level++ {
        levelN >>= 1
        total -= levelN
    }
    return level
}

level := 0
    for k < total {
        levelN >>= 1
        total -= levelN
        level++
    }

func (sl *SkipList[K, V]) randomLevel() int {
    total := uint64(1)<<uint64(skipListMaxLevel) - 1 // 2^n-1
    k := sl.rander.Uint64() % total
    return skipListMaxLevel - bits.Len64(k) + 1
}

// Len64 returns the minimum number of bits required to represent x; 
// the result is 0 for x == 0.
func Len64(x uint64) (n int) {
    // ...
    return n + int(len8tab[x])
}

// Insert inserts a key-value pair into the skiplist.
// If the key is already in the skip list, it's value will be updated.
func (sl *SkipList[K, V]) Insert(key K, value V) {
    // 处理key已存在的情况，略去

    level := sl.randomLevel()
    node = newSkipListNode(level, key, value)

    // 插入链表，略去

    if level > sl.level {
        // Increase the level
        for i := sl.level; i < level; i++ {
            sl.head.next[i] = node
        }
        sl.level = level
    }
    sl.len++
}

func (sl *Skiplist) findPrevNodes(key interface{}) []*Node {
    prevs := sl.prevNodesCache
    prev := &sl.head
    for i := sl.maxLevel - 1; i >= 0; i-- {
        if sl.head.next[i] != nil {
            for next := prev.next[i]; next != nil; next = next.next[i] {
                if sl.keyCmp(next.key, key) >= 0 {
                    break
                }
                prev = &next.Node
            }
        }
        prevs[i] = prev
    }
    return prevs
}

// Insert inserts a key-value pair into the skiplist
func (sl *Skiplist) Insert(key, value interface{}) {
    prevs := sl.findPrevNodes(key)

    if prevs[0].next[0] != nil && sl.keyCmp(prevs[0].next[0].key, key) == 0 {
        // 如果相等，其实prevs就没用了，但是findPrevNodes里依然进行了查询
        // same key, update value
        prevs[0].next[0].value = value
        return
    }
    ...
}

// findInsertPoint returns (*node, nil) to the existed node if the key exists,
// or (nil, []*node) to the previous nodes if the key doesn't exist
func (sl *skipListOrdered[K, V]) findInsertPoint(key K) (*skipListNode[K, V], []*skipListNode[K, V]) {
    prevs := sl.prevsCache[0:sl.level]
    prev := &sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for next := prev.next[i]; next != nil; next = next.next[i] {
            if next.key == key {
                // Key 已经存在，停止搜索
                return next, nil
            }
            if next.key > key {
                // All other node in this level must be greater than the key,
                // search the next level.
                break
            }
            prev = next
        }
        prevs[i] = prev
    }
    return nil, prevs
}

// Insert inserts a key-value pair into the skiplist.
// If the key is already in the skip list, it's value will be updated.
func (sl *SkipList[K, V]) Insert(key K, value V) {
    node, prevs := sl.impl.findInsertPoint(key)
    if node != nil {
        // Already exist, update the value
        node.value = value
        return
    }
    // 生成及插入新节点，略去
}

// Get returns the value associated with the passed key if the key is in the skiplist, otherwise returns nil
func (sl *Skiplist) Get(key interface{}) interface{} {
    var pre = &sl.head
    for i := sl.maxLevel - 1; i >= 0; i-- {
        cur := pre.next[i]
        for ; cur != nil; cur = cur.next[i] {
            cmpRet := sl.keyCmp(cur.key, key)
            if cmpRet == 0 {
                return cur.value
            }
            if cmpRet > 0 {
                break
            }
            pre = &cur.Node
        }
    }
    return nil
}

type skipListImpl[K any, V any] interface {
    findNode(key K) *skipListNode[K, V]
    lowerBound(key K) *skipListNode[K, V]
    upperBound(key K) *skipListNode[K, V]
    findInsertPoint(key K) (*skipListNode[K, V], []*skipListNode[K, V])
    findRemovePoint(key K) (*skipListNode[K, V], []*skipListNode[K, V])
}

// NewSkipList creates a new SkipList for Ordered key type.
func NewSkipList[K Ordered, V any]() *SkipList[K, V] {
    sl := skipListOrdered[K, V]{}
    sl.init()
    sl.impl = (skipListImpl[K, V])(&sl)
    return &sl.SkipList
}

// NewSkipListFunc creates a new SkipList with specified compare function keyCmp.
func NewSkipListFunc[K any, V any](keyCmp CompareFn[K]) *SkipList[K, V] {
    sl := skipListFunc[K, V]{}
    sl.init()
    sl.keyCmp = keyCmp
    sl.impl = skipListImpl[K, V](&sl)
    return &sl.SkipList
}

// newSkipListNode creates a new node initialized with specified key, value and next slice.
func newSkipListNode[K any, V any](level int, key K, value V) *skipListNode[K, V] {
    switch level {
    case 1:
        n := struct {
            head skipListNode[K, V]
            nexts [1]*skipListNode[K, V]
        }{head: skipListNode[K, V]{key, value, nil}}
        n.head.next = n.nexts[:]
        return &n.head
    case 2:
        n := struct {
            head skipListNode[K, V]
            nexts [2]*skipListNode[K, V]
        }{head: skipListNode[K, V]{key, value, nil}}
        n.head.next = n.nexts[:]
        return &n.head
    // 一直到 case 40 ...
    }
}

template <typename K, typename V>
struct Node {
  K key;
  V value;
  size_t level;
  Node* nexts[0];
  SkipListNode(key, V value) : level(level), key(std::move(key)), value(std::move(value)) {}
};

template <typename K, typename V, int N> // 注意 N 可以作为模板参数
struct NodeN : public Node {
  NodeN(K key, V value) : Node(N, key, value) {}
  Node* nexts[N] = {};
};

Node* NewNode(int level, K key, V value) {
  switch (level) {
    case 1: return new NodeN<K, V, 1>(key, value);
    case 2: return new NodeN<K, V, 2>(key, value);
    case 3: return new NodeN<K, V, 3>(key, value);
    ...
  }
}

Node* NewNode(int level, K key, V value) {
  auto p = malloc(sizeof(Node*) + level * sizeof(Node*));
  return new(p) Node(std::move(key), std::move(value));
}