Skip List 来自William Pugh 的一篇论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。一个Skip List 如下图所示(图片来自维基百科)：
Skip List
Skip List 是链表的一种拓展，上层由不同高度的指针组成，通过上层指针跳跃实现时间复杂度为 O(log(N)) 的查找。这个特性适用于对有序 Key - Value 类型进行查找、加入等操作。大名鼎鼎的缓存中间件 Redis 的 Zset 类型(有序集合)在数据量满足下面两个条件时会采用跳跃链表来实现：

  • 集合保存的元素数量 >= 128 个时
  • 集合存在元素长度 >= 64 字节时

关于跳表的原理详细讲解可以参考这个视频, 这里展示一下我自己实现的 Java 版跳表

1. 成员变量

// 跳表长高几率
private final float upgradePercentage = 0.25F;
// 跳表最大层高
private final int maxLevel = 16;
// 当前跳表最大层数
private int level;
// 当前跳表元素个数
private int length;
// 跳表头节点
private final Node<T> head;
// 随机数生成
private final Random random = new Random();

2. 跳表Node定义

static class Node<T> {
    // 可排序的key, 目前暂用int型
    private Integer key;
    // 节点value
    private T value;
    // 每层指向后续节点的指针
    private Node<T>[] forwards;

    public Node(Integer key, T value, int level) {
        this.key = key;
        this.value = value;
        this.forwards = new Node[level];
    }
    public Node(int level) {
        this.forwards = new Node[level];
    }
}

3. 构造方法与一些其他方法

这里稍微提一下关于长高因子的设定, 上面成员变量中设定的为25%, 而一般大家认识的跳表应该取的是50%

长高因子的取值对于跳表查找时间与节点前向指针数量的影响曾经也有数学大佬研究过，如下表所示

长高概率 pNormalized Search TimesAvg pointer per node
1/212
1/e0.94..1.58..
1/411.33..
1/81.33..1.14..
1/1621.07..
public SkipList() {
    // 头结点仅作为哨兵节点
    this.head = new Node<>(maxLevel);
    this.level = 0;
    this.length = 0;
}

public int size() {
    return this.length;
}

// 获取层高的逻辑
private int getRandomLevel() {
    int level = 1;
    while (random.nextFloat() < upgradePercentage && level < maxLevel) {
        level++;
    }
    return level;
}

4. 主要方法之一: add 方法

public T add(int key, T value) {
    // 记录一下插入位置每层前一位置的节点, 需要将他们的指向全部更新为插入节点
    Node<T>[] toUpdate = new Node[maxLevel];
    Node<T> h = this.head;
    for (int i = this.level - 1; i >= 0; i--) {
        while (h.forwards[i] != null && h.forwards[i].key < key)
            h = h.forwards[i];

        toUpdate[i] = h;
    }
    h = h.forwards[0];

    // 如果key冲突了则替换value
    if (h != null && h.key == key) {
        h.value = value;
        return h.value;
    }

    int level = getRandomLevel();
    // 如果高度超过了头结点, 则固定只比头结点高一层, 头结点也长高与其对应
    if (level > this.level) {
        level = this.level + 1;
        toUpdate[this.level] = this.head;
        this.level = level;
    }
    // 插入节点并修改前序节点的指针
    Node<T> node = new Node<>(key, value, level);
    for (int i = 0; i < level; i++) {
        node.forwards[i] = toUpdate[i].forwards[i];
        toUpdate[i].forwards[i] = node;
    }
    this.length++;
    return node.value;
}

5. 主要方法之二: get 方法

public T get(int key) {
    Node<T> h = this.head;
    // 拿到头结点之后, 从最顶层开始遍历, 进行类二分查找的过程, 找到第一个比key小的节点
    for (int level = this.level - 1; level >= 0; level--) {
        while (h.forwards[level] != null && h.forwards[level].key < key)
            h = h.forwards[level];
    }
    
    // 定位到节点后还需要比较key是否相同
    h = h.forwards[0];
    if (h != null && h.key == key)
        return h.value;
    return null;
}

6. 主要方法之三: delete 方法

主要的逻辑还是先定位位置并且保存前序节点, 再删除节点后修改所有前序节点~看到这里相信大家没有注释也能轻松看懂了

public T delete(int key) {
    Node<T>[] update = new Node[maxLevel];
    Node<T> h = this.head;
    for (int i = update.length - 1; i >= 0; i--) {
        while (h.forwards[i] != null && h.forwards[i].key < key)
            h = h.forwards[i];
        update[i] = h;
    }

    h = h.forwards[0];
    if (h != null && h.key == key) {
        for (int i = 0; i < this.level; i++) {
            if (update[i].forwards[i] != h)
                return null;
            update[i].forwards[i] = h.forwards[i];
        }
        this.length--;
    }
    return h == null ? null : h.value;
}

7. 代码总体

public class SkipList<T> {

    // 跳表长高几率
    private final float upgradePercentage = 0.5F;
    // 跳表最大层高
    private final int maxLevel = 16;

    // 当前跳表最大层数
    private int level;
    // 当前跳表元素个数
    private int length;
    // 跳表头节点
    private final Node<T> head;
    // 随机数生成
    private final Random random = new Random();


    static class Node<T> {
        // 可排序的key, 目前暂用int型
        private Integer key;
        // 节点value
        private T value;
        // 多个指向其他节点的指针
        private Node<T>[] forwards;

        public Node(Integer key, T value, int level) {
            this.key = key;
            this.value = value;
            this.forwards = new Node[level];
        }
        public Node(int level) {
            this.forwards = new Node[level];
        }
    }

    public SkipList() {
        // 头结点仅作为哨兵节点
        this.head = new Node<>(maxLevel);
        this.level = 0;
        this.length = 0;
    }


    private int getRandomLevel() {
        int level = 1;
        while (random.nextFloat() < upgradePercentage && level < maxLevel) {
            level++;
        }
        return level;
    }

    public T add(int key, T value) {
        // 记录一下插入位置每层前一位置的节点, 需要将他们的指向全部更新为插入节点
        Node<T>[] toUpdate = new Node[maxLevel];
        Node<T> h = this.head;
        for (int i = this.level - 1; i >= 0; i--) {
            while (h.forwards[i] != null && h.forwards[i].key < key)
                h = h.forwards[i];

            toUpdate[i] = h;
        }
        h = h.forwards[0];

        // 如果key冲突了则替换value
        if (h != null && h.key == key) {
            h.value = value;
            return h.value;
        }

        int level = getRandomLevel();
        // 如果高度超过了头结点, 则固定只比头结点高一层, 头结点也长高与其对应
        if (level > this.level) {
            level = this.level + 1;
            toUpdate[this.level] = this.head;
            this.level = level;
        }
        // 插入节点并修改前面节点的指针
        Node<T> node = new Node<>(key, value, level);
        for (int i = 0; i < level; i++) {
            node.forwards[i] = toUpdate[i].forwards[i];
            toUpdate[i].forwards[i] = node;
        }
        this.length++;
        return node.value;
    }

    public T get(int key) {
        Node<T> h = this.head;
        for (int level = this.level - 1; level >= 0; level--) {
            while (h.forwards[level] != null && h.forwards[level].key < key)
                h = h.forwards[level];
        }

        h = h.forwards[0];
        if (h != null && h.key == key)
            return h.value;
        return null;
    }

    public int size() {
        return this.length;
    }

    public T delete(int key) {
        Node<T>[] update = new Node[maxLevel];
        Node<T> h = this.head;
        for (int i = update.length - 1; i >= 0; i--) {
            while (h.forwards[i] != null && h.forwards[i].key < key)
                h = h.forwards[i];
            update[i] = h;
        }

        h = h.forwards[0];
        if (h != null && h.key == key) {
            for (int i = 0; i < this.level; i++) {
                if (update[i].forwards[i] != h)
                    return null;
                update[i].forwards[i] = h.forwards[i];
            }
            this.length--;
        }
        return h == null ? null : h.value;
    }
}

Test一下

public class TestSkipList {
    public static void main(String[] args) {
        SkipList<Integer> skipList = new SkipList<>();
        skipList.add(0, 1);
        skipList.add(1, 2);
        skipList.add(1, 3);
        System.out.println(skipList.get(0));
        System.out.println(skipList.get(1));
        skipList.delete(1);
        System.out.println(skipList.get(1));
    }
}

输出：

1
3
null

Process finished with exit code 0

完成!

Last modification：March 22nd, 2022 at 05:18 pm
© 允许规范转载