2C.md

跳跃链表

普通链表在查找上没有什么优势，但只要经过适当的改造，链表也能有O(logN)级的查找性能。

多级链路

跳跃链表的特点在于其节点有若干个指针域，可以构成疏密不等的多级链路。

type bNode[T constraints.Ordered] struct {
    next []*bNode[T]        //若干个指针域
}
type lNode[T constraints.Ordered] struct {
    bNode[T]
    key T
}
type skipList[T constraints.Ordered] struct {
    bNode[T]                //head
    size        int
    floor, ceil int         //非零，当前级别容量的上下界
    magic       uint32      //随机状态
    knots       []*bNode[T] //临时存储
}

跳跃查找

利用多级链路，每次从稀疏的高级链路开始，跳跃前进：

func (l *skipList[T]) Search(key T) bool {
    knot, node := &l.bNode, (*lNode[T])(nil)
    for i := len(l.next) - 1; i >= 0; i-- {
        for node = knot.next[i].asLeaf(); node != nil && node.key < key; node = knot.next[i].asLeaf() {
            knot = &node.bNode
    }   }
    return node != nil && node.key == key
}

我们通过5万数列的查找可以看出，这种跳跃式相对传统链表已经有了质的变化。

LinkedList: 3.7722158s
SkipList:   7.0004ms

投机者的胜利

　　跳跃链表的核心思想就是用不对称的节点构造多级链路，但是，怎么确定每个节点的级别呢？这个问题和数组快速排序中怎么确定分界点一样棘手。于是，从宏观上划定高级节点所占的比例之后，我们再次求助于骰子。

func (l *skipList[T]) Insert(key T) bool {
    node := l.search(key)
    if node != nil && node.key == key {
        return false
    }

    level := 1
    for level < len(l.next) &&
        l.rand() <= (math.MaxUint32/uint32(LevelFactor)) {
        level++             //投机决定节点级别
    }
    node = newLeaf[T](level)
    node.key = key
    for i := 0; i < level; i++ {
        node.next[i] = l.knots[i].next[i]
        l.knots[i].next[i] = &node.bNode
    }

    l.size++
    if l.size == l.ceil {   //升级
        l.floor = l.ceil
        l.ceil *= LevelFactor
        l.next = append(l.next, nil)
        l.knots = append(l.knots, nil)
    }
    return true
}

高级话题

　　光凭O(logN)的平均查找性能，不足以让跳跃链表立足于强手之林。不过作为链表家族的一员，跳跃链表也比较容易实现顺序遍历和无锁并行（尽管这里给的实现并非不支持），在某些场景下比树结构更有优势。

---

目录　上一节　下一节