跳表 - 简明教程 in Python

# 1. 什么是跳表

跳表（Skip List）是基于链表 + 随机化实现的一个有序数据结构，可以达到平均 O(logN) 的查找、插入、删除效率，在实际运行中的效率往往超过 AVL 等平衡二叉树，而且其实现相对更简单、内存消耗更低。

Redis 的 ZSET 底层实现就是用的 Skip List，这里是 [Antirez对此的说明]( https://news.ycombinator.com/item?id=1171423) 。

这是一个典型的跳表：

[0] -> 0 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9 -> nil
[1] -> 0 ------> 3 ------> 5 ------> 7 ------> nil
[2]----------------------> 5-----------------> nil

解释一下：

1. SkipList 是一个多层的链表

2. 第[0]层的链表包含所有节点，其他层的链表包含部分节点，层次越高，节点越少

3. 每层链表之间会共享相同的节点（节省内存，但为了方便展示，每一层都输出了它的值）

4. 对于某个节点，在插入时通过概率判断它最高会出现在哪一层，并且也会出现在之下的每一层

通过这样的设计，当需要查找某个 key 时，可以从最高层的链表开始往前找，在这一层遇到末尾或者大于 key 的节点时往下走一个层，直到找到 key 节点。

例如:

# 2. 跳表的节点

从上面的描述，我们大概可以知道 (1) 每个节点需要保存一个 key; (2) 每个节点需要有多个next指针 (3) 其 next 指针的数量会在插入时确定

因此我们可以用下面这个 class 来表示节点:

class Node(object)
    def __init__(self, height, key):
        self.key = key
        self.next = [None] * height

    def height(self):
        return self.height()

# 3. 创建跳表

一个新创建的跳表是没有节点的。但为了实现的简单起见，可以添加一个头节点：

class SkipList(object):
    def __init__(self):
        self.head = Node(0, None) #头节点高度为0，不需要key

到目前为止都特别简单，但是还什么也干不了。

# 4. 创建节点

创建节点时，需要先按一定的概率分布确定其高度。

为了保证高层的节点比低层少，我们可以用这样的概率分布：

引用

Height(n) = p^n

实现其实非常简单：

import random

def randomHeight(self, p = 0.5):
    height = 1
    while random.uniform(0, 1) < p and self.head.height() >= height:
        height += 1
    return height

这样可以保证平均的路径长度是 log(n) 。

精确一点的话，实际上是 log(n-1, 1/p) / p，也就是说， p 的选择会影响跳表层数、平均路径长度。

具体的计算比较复杂，有兴趣可以参考跳表的原论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。（TL;DR）

然后我们就可以这样来创建一个新的节点：

node = Node(self.randomHeight(), key)

# 5. 添加节点

如果只是为空跳表添加一个新的节点，只要更新头结点的每一个next指针：

def insertFirstNode(self, key):
    node = Node(self.randomHeight(), key)
    while node.height > self.head.height():
        self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表

    for level in range(node.height()):
        node.next[level] = self.head.next[level]
        self.head.next[level] = node

但很显然这个方法只能用一次。

如果跳表中已经有多个节点，那我们就必须找到每一层中适合插入的位置：

def getUpdateList(self, key):
    update = [None] * self.head.height()
    for level in range(len(update)):
        x = self.head
        while x.next[level] is not None and x.next[level].key < key:
            x = x.next[level]
        update[level] = x
    return update

这个函数返回一个 update 节点数组，其中的每个节点都是在这一层中小于 key 的最后一个节点。

也就是说，在 level = i 层，总是可以把新的节点插入 update[i] 之后：

def insert(self, key):
    node = Node(self.randomHeight(), key)
    while node.height > self.head.height():
        self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表

    update = self.getUpdateList(key)
    next0 = update[0].next[0]
    if next0 is not None and next0.key == key:
        return # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。

    for level in range(node.height()):
        node.next[level] = update[level].next[level]
        update[level].next[level] = node

但是由于这一版 getUpdateList 是 O(n) 的，插入效率并没有达到跳表的设计目标。

# 6. 添加节点++

考虑这一点：跳表的每一层都是有序的。

也就是说，我们在找到 update[n] = x 以后，其实可以从节点 x 的 n - 1 层继续查找来查找 update[n-1] 。

由于查找路径的评价长度是 log(N) ，所以我们可以实现一个更快的 getUpdateList 方法

注意，需要从最高层开始查

def getUpdateList(self, key):
    update = [None] * self.head.height()
    x = self.head
    for level in reversed(range(len(update))):
        while x.next[level] is not None and x.next[level].key < key:
            x = x.next[level]
        update[level] = x
    return update

# 7. 里程碑1

把上面的代码整合起来，我们就可以得到第一版跳表代码：能够插入节点。

为了更好地展示我们的成果，我们可以用这样一个函数，把链表按第1节的例子样式输出：

def dump(self):
    for i in range(self.head.height()):
        sys.stdout.write('[H]')
        x = self.head.next[0]
        y = self.head.next[i]
        while x is not None:
            s = ' -> %s' % x.key
            if x is y:
                y = y.next[i]
            else:
                s = '-' * len(s)
            x = x.next[0]
            sys.stdout.write(s)
        print ' -> <nil>'
    print

试试看：

sl = SkipList()
for i in range(10):
    sl.insert(sl)
    s1.dump()

[H] -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> <nil>
[H]----- -> 1 -> 2 -> 3---------- -> 6 -> 7---------- -> <nil>
[H]---------- -> 2-------------------- -> 7---------- -> <nil>

多尝试几次，以及选择不同的 p 值，可以观察生成跳表的区别。

# 8. 查找节点

实际上查找节点的过程，已经包含在 insert 的实现里了：

def find(self, key):
    update = self.getUpdateList(key)
    if len(update) == 0:
        return None

    next0 = update[0].next[0]
    if next0 is not None and next0.key == key:
        return next0 # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。
    else:
        return None

# 9. 删除节点

既然已经能找出 update 节点数组，在 level = i 层，只要判断 update[i].next[i] 是否等于要删除的 key 就可以了：

def remove(self, key):
    update = self.getUpdateList(key)
    for i, node in enumerate(update):
        if node.next[i] is not None and node.next[i].key == key:
            node.next[i] = node.next[i].next[i]

# 10. 里程碑2

整合 find 和 update 数组，就可以实现跳表的基础操作了，试试看：

node = sl.find(3)
print node

for i in range(7, 14):
    sl.remove(i)
    sl.dump()

# 11. 其他

我们在 Node 中只添加了一个 key 属性，在具体的实现中，我们往往可能需要针对 key 存储一个 value，例如 Python 自带的 dict 实现。改造起来也很简单:

1. node 中添加一个 value 属性，并且添加相应的初始化逻辑(__init__方法)

2. 将 SkipList.insert 修改为 `insert(self, key, value)`，在新建 Node 时指定其 value

3. 再添加一个 `update(self, key, value)` API，方便调用方的使用

4. 可以考虑针对语言适配，例如实现 python 的 __getitem__ 、 __setitem__ 等魔术方法

# 12. 完整代码

#coding:utf-8

import random

class Node(object):
    def __init__(self, height, key=None):
        self.key = key
        self.next = [None] * height

    def height(self):
        return len(self.next)

class SkipList(object):
    def __init__(self):
        self.head = Node(0, None) #头节点高度为0，不需要key

    def randomHeight(self, p = 0.5):
        height = 1
        while random.uniform(0, 1) < p and self.head.height() >= height:
            height += 1
        return height

    def insert(self, key):
        node = Node(self.randomHeight(), key)
        print node.height(), node.key
        while node.height() > self.head.height():
            self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表

        update = self.getUpdateList(key)
        if update[0].next[0] is not None and update[0].next[0].key == key:
            return # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。

        for level in range(node.height()):
            node.next[level] = update[level].next[level]
            update[level].next[level] = node


    def getUpdateList(self, key):
        update = [None] * self.head.height()
        x = self.head
        for level in reversed(range(len(update))):
            while x.next[level] is not None and x.next[level].key < key:
                x = x.next[level]
            update[level] = x
        return update

    def dump(self):
        for i in range(self.head.height()):
            sys.stdout.write('[H]')
            x = self.head.next[0]
            y = self.head.next[i]
            while x is not None:
                s = ' -> %s' % x.key
                if x is y:
                    y = y.next[i]
                else:
                    s = '-' * len(s)
                x = x.next[0]
                sys.stdout.write(s)
            print ' -> <nil>'
        print

    def find(self, key):
        update = self.getUpdateList(key)
        if len(update) == 0:
            return None

        next0 = update[0].next[0]
        if next0 is not None and next0.key == key:
            return next0 # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。
        else:
            return None

    def remove(self, key):
        update = self.getUpdateList(key)
        for i, node in enumerate(update):
            if node.next[i] is not None and node.next[i].key == key:
                node.next[i] = node.next[i].next[i]

完。

转载请注明出自，如是转载文则注明原出处，谢谢:)

RSS订阅地址: http://www.felix021.com/blog/feed.php 。