Version: Next

跳表

思考

一个有序链表，其搜索、添加、删除操作的平均时间复杂度是多少？

沿链表遍历时间复杂度为 O(n)

能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低到 O(logn) ?

数组可以使用二分搜索
- 因为数组支持随机访问，偏移量随便设，且不管偏移多大，复杂度都是 O(1)
链表不能直接使用二分搜索
- 因为链表不支持随机访问

是否存在其他方法能让有序链表的搜索、添加、删除操作的平均时间复杂度降低到 O(logn) ？

跳表——Skip List

跳表
又称 跳跃表、跳跃列表，是在 有序链表 的基础上增加了跳跃的功能
由 William Pugh 于 1990 年发布，设计初衷是为了取代平衡树（如红黑树）
Redis 中的 SortedSet、LevelDB 中的 MemTable 都使用了跳表
对比平衡树
跳表的实现和维护都更简单
跳表的搜索、删除、添加操作平均时间复杂度都是 O(logn)

使用跳表优化链表

有一根普通的有序单向链表如图所示

在它的基础上，再融入一根新的单向链表，只选取原先的部分节点

如法炮制，可以再来几根

如果要查找元素 19

跳表的实现

实际应用中，节点存储的数据类型通常为 Key - Value 键值对
一般认为节点上存储的具有 可比较性 的数据是其 Key，为跳表设定泛型为 <K, V>

成员变量

变量	含义
`int size`	元素个数
`Comparator<K> comparator`	`Key` 的比较器，允许外部传入比较器来指明节点的 `Key` 按照什么规则进行比较
`Node<K, V> first`	虚拟头结点其指向的所有下一个节点数目与跳表层数相等通常会设定上限，如 Redis 限制为 `32`层
`static final int MAX_LEVEL`	跳表的最大层数，限制为 `32`
`int level`	跳表的有效层数
`static final double P`	用于插入节点，决定节点层数时使用的随机数（实现随机层数）

构造方法

接收外部传入的比较器 comparator，也可以不传比较器，通过后续的 compare() 比较方法来决定具体的比较规则
创建虚拟头结点实例化对象，key-value 都为 null、头结点的高度设置为跳表最大高度 MAX_LEVEL
初始化虚拟头结点的 nexts 属性，即其指向的所有节点的数组，数组长度就设置为 跳表层数上限

构造方法

public MySkipList(Comparator<K> comparator) {
    this.comparator = comparator;
    first = new Node<>(null, null, MAX_LEVEL);
    first.nexts = new Node[MAX_LEVEL];
}

public MySkipList() {
    this(null);
}

比较方法

如果外部传入了比较器，就是用外部比较器
如果外部没传入比较器，则强制要求默认的 key 类型 K 本身就具有 可比性Comparable，直接调用其接口方法 compareTo() 进行比较

compare方法

/**
 * 比较方法，如果外部传入了比较器，就是用外部比较器
 * 如果外部没传入比较器，则强制要求默认的 key 类型 K 本身就具有可比性，直接调用其进行比较
 *
 * @param key1 键1
 * @param key2 键2
 * @return 比较结果
 */
private int compare(K key1, K key2) {
    return this.comparator != null ? this.comparator.compare(key1, key2)
            : ((Comparable<K>) key1).compareTo(key2);
}

键判空方法

由于强制要求 key 具有可比较性，所以 key 不能为 null

keyCheck方法

/**
 * key 判空方法 由于强制要求 key 具有可比较性，所以 key 不能为 null
 *
 * @param key 键
 */
private void keyCheck(K key) {
    if (key == null) throw new IllegalArgumentException("Key 不允许为空");
}

查找方法

输入 Key 找到其对应的节点，并取出 Value
Key 判空
从所有有效层的最上层开始查找，不断向右查找
当前节点 key 大于目标 key，或到达 尾节点：返回上一个节点，进入下一层
当前节点 key 小于目标 key：继续前往下一个节点，直到找到 key 大于等于 目标 key 或到达 尾节点
重复上一步，直到
无层可进：说明目标 key 不在当前跳表中
某节点 key 等于目标 key：在跳表中找到了目标 key

get方法实现元素查找

public V get(K key) {
    keyCheck(key); // 如果 key 为空，会在这里抛出非法参数异常
    // 当前节点指针
    Node<K, V> node = first;
    // 从最高的有效层开始搜索 其索引时 `有效层数 - 1`
    for (int i = level - 1; i >= 0; i--) {
        // 拿到 下标为 i 的那一层的 第一个实际节点 first.nexts[i]
        //  拿这个节点的 key 和 目标Key进行比较
        int compareResult = -1;
        // 如果当前节点不是尾结点  并且（and） 当前节点 key 小于 目标key
        while (node.nexts[i] != null && (compareResult = compare(node.nexts[i].key, key)) < 0) {
            // 则前往当前节点的下一个节点
            node = node.nexts[i];
        }
        // 来到这里，说明当前节点key 大于等于 目标key 了
        if (compareResult == 0) // 两 key 相等，找到了，直接返回 value
            return node.nexts[i].value;
        // 来到这里，表示 当前 key 大于 目标key：返回上个节点，进入下一层
        // - 返回上一节点：当前node指向的就是"上一个节点"，所以啥也不用写
        // - 进入下一层，就是 i--：根据for循环，啥也不用写
    }
    
    return null; // 没找到，返回 null
}

随机层数方法

在 插入节点 时，新节点的层数完全是随机的，因此需要写一个方法，来生成随机的层数
新节点的层数：完全随机，就是说想弄几层弄几层。实际中，采取「抛硬币」的方法
在跳表类里设置一个 double 类型的常量 P，值设置为 0.25
使用Math.random()方法生成 [0, 1)之间的随机数，只要 随机数 < P，就将 层数加 1
但生成的随机层不能超过设置的最大层数：randomLevel < MAX_LEVEL

生成随机层数

/**
 * 为插入节点方法提供节点的随机层数
 *
 * @return 生成的随机层数
 */
private int randomLevel() {
    int randomLevel = 1; // 起码得有 1 层
    while (Math.random() < P && randomLevel < MAX_LEVEL) randomLevel++;
    return randomLevel;
}

添加方法

插入一个 Key-Value 形式的键值对数据
首先对 Key 进行判空，不允许存储空键
接下来的若干步骤与 查找方法 一模一样，搜索要插入元素的 key
特殊情况：找到了这个 key，说明要插入的这个元素的 key 之前在跳表里就存在，那么就更新一下其 value，将旧value 返回，添加完毕
一般情况：找不到这个 key，于是会跑完所有有效层，发现无层可去，此时的 node 就指向了要插入节点的 前驱结点，简言之 node 就是前驱结点
决定新添加节点的层数 newNodeLevel：调用 随机层数方法 来生成
为新节点创建 Node<K, V> 数组 nexts，将数组的 长度 设置为上一步得到的 随机层数
维护新节点的 前驱节点 与 后继节点：
前驱结点：新节点左边的一系列节点，还需要知道这些节点的 nexts 数组中的哪个 下标 （第几个）应当指向新节点，如下图所示的情况下，我们就关心图中所示的 4 个 nexts 数组元素
具体哪些节点是我们关心的前驱节点：观察发现，就是那些会 触发层数下降 的节点。进一步观察可知：
此节点的 key 一定小于要插入新节点的 key，并且此节点当前层的 next 节点的 key 一定大于要插入的新节点 key ，或 next 节点是 空节点
当前触发层数下降的节点 和 这个节点当前层的 next 节点 之间，正好就是插入新节点的位置
需要保存的 nexts 元素个数 = 触发层数下降的次数：也即，一旦触发层数下降，就记录当前节点当前层的 nexts 数组中的元素，它指向了当前层的后继节点
存储前驱节点的实现方法：创建一个 Node[] prevNodes 数组，记录要插入新街点的前驱节点，数组大小为当前跳表的有效层数 level
示例：根据上图的例子，prevNodes 的内容应当为：prevNodes[0] = key12节点 表示要插入新节点在下标为 0 的层的前驱节点是 key = 12的节点；prevNodes[1] = key9节点 表示要插入新节点在下标为 1 的层的前驱节点时 key = 9 的节点，以此类推。
实现：prevNodes[i] = node;
实现前驱与后继关系的维护：遍历有效层
让新节点在当前层的 next 指向 新节点当前层前驱节点 原先的后继节点newNode.nexts[i] = prevNodes[i].nexts[i];
新节点当前层前驱结点 的后继 next 指向 新节点
prevNodes[i].nexts[i] = newNode
特殊情况：
当前跳表的有效层数 level 大于新插入节点随机生成的层数 newNodeLevel 会造成 prevNodes[]的数组长度大于 newNodeLevel，不会造成数组越界
不需要做处理
当前跳表的有效层数 level 小于新插入节点随机生成的层数 newNodeLevel ：即 level < newNodeLevel
会造成 prevNodes[]的数组长度小于 newNodeLevel，维护新节点前驱后继关系时，会发生数组越界
新节点 高出 有效层数level 的部分（newNodeLevel - level），这部分其当前层的 前驱就是虚拟头节点、后继就是尾空节点（默认就是空不用处理）
添加新节点后，维护跳表的有效层数：插入的新节点，其高度是随机生成的，有可能超过先前的有效高度，因此，在插入过后，当前跳表的有效层数应当取 先前有效层数 与 新节点层数 二者中的较大者 Math.max(level, newNodeLevel)
跳表的有效元素数加 1：size++;

添加方法

/**
 * 将值存入目标键。返回先前的值
 *
 * @param key   键
 * @param value 值
 * @return 先前的值
 */
public V put(K key, V value) {
    keyCheck(key); // 如果 key 为空，会在这里抛出非法参数异常
    // 当前节点指针
    Node<K, V> node = first;
    // 用来记录要插入新节点的前驱节点，数组大小为当前跳表的有效层数 level
    Node<K, V>[] prevNodes = new Node[level];
    // 从最高的有效层开始搜索 其索引时 `有效层数 - 1`
    for (int i = level - 1; i >= 0; i--) {
        // 拿到 下标为 i 的那一层的 第一个实际节点 first.nexts[i]
        //  拿这个节点的 key 和 目标Key进行比较
        int compareResult = -1;
        // 如果当前节点不是尾结点  并且（and） 当前节点 key 小于 目标key
        while (node.nexts[i] != null && (compareResult = compare(node.nexts[i].key, key)) < 0) {
            // 则前往当前节点的下一个节点
            node = node.nexts[i];
        }
        // 来到这里，说明当前节点key 大于等于 目标key 了
        if (compareResult == 0) {// 两 key 相等，说明要插入的 key 之前就存在了，那么直接更新 value
            V oldValue = node.nexts[i].value;
            node.nexts[i].value = value; // 新值覆盖旧值
            return oldValue; // 返回被覆盖的旧值
        }
        // 来到这里，表示 当前 key 大于 目标key：返回上个节点，进入下一层
        // 一旦触发了层下降，则记录前驱节点
        prevNodes[i] = node;
        // - 返回上一节点：当前node指向的就是"上一个节点"，所以啥也不用写
        // - 进入下一层，就是 i--：根据for循环，啥也不用写
    }
    // 来到这里，说明要插入元素的 key 对于当前跳表是 全新的
    // 并且，此时的 node 就指向了我们要插入新节点的 前驱结点
    // 添加新节点，传入键、值，使用 随机生成层数方法 来生成新节点的层数
    int newNodeLevel = randomLevel(); // 生成的新层数
    Node<K, V> newNode = new Node<>(key, value, newNodeLevel);
    // 插入：维护前后节点指针
    for (int i = 0; i < newNodeLevel; i++) { // 遍历有效层
        if (i >= level) { // 特殊情况：新节点的高度 超过 跳表有效层数
            first.nexts[i] = newNode; // newNode在当前层的前驱是 头节点 first
            // newNode 在当前层的后继 nexts[i] 为 空null，本来就是null所以不用写
        } else { // 新节点层高 小于 跳表有效层数 的情况
            // 让新节点在当前层的 `next` 指向 `新节点当前层前驱节点` *原先的后继节点*
            newNode.nexts[i] = prevNodes[i].nexts[i];
            // `新节点当前层前驱结点` 的 后继 `next` 指向 `新节点`
            prevNodes[i].nexts[i] = newNode;
        }
    }

    size++; // 有效节点数增加
    level = Math.max(level, newNodeLevel); // 维护跳表的有效层数

    return null;
}

删除方法

与添加方法类似
在添加方法的基础上，移除 发现 key 相等就更新 value 的代码
依旧逐层遍历，查找目标 key，一旦触发层下降，就记录前驱节点
特殊情况：对于删除方法，要特殊考虑要删除的 key 根本不存在的情况，使用 boolean exist 来记录
实现：将添加方法中，发现相同 key 就更新 value 并返回的代码，修改为发现相同 key 就将 exist 设置为 true 的代码。if (compareResult == 0) exist = true;
遍历完毕，检查 exist 的值
false：表示要删除的 key 根本不存在，直接返回 null，方法执行完毕
true：表示要删除的 key 确实存在
删除目标节点
维护前驱、后继关系
获取被删除节点的高度：获取被删除节点的高度，即被删除节点的 nexts[] 数组的长度
遍历被删除节点的高度：在每一层上，将被删除节点的前驱的 next ，指向被删除节点的后继。prevNodes[i].nexts[i] = deleteNode.nexts[i]
更新跳表的有效层数 level：如果被删除节点的高度之前是跳表中最高的，那么删除只会，会造成跳表有效层数的下降
从先前的 最高有效层 开始，一层一层检查头结点 first 在当前层的 next 是否为 尾空节点
如果在当前层，first.nexts[当前层index] 确实指向 null，说明当前层已经 无效，有效层数 level 应当减少
返回被删除节点的 value：node 指向了被删除节点的前驱，那么被删除节点就是 node 在下标为 0 层的 next，则要返回的 value 就是 node.nexts[0].value

删除方法

public V remove(K key) {
    keyCheck(key); // 如果 key 为空，会在这里抛出非法参数异常
    // 当前节点指针
    Node<K, V> node = first;
    // 用来记录要删除节点的前驱节点，数组大小为当前跳表的有效层数 level
    Node<K, V>[] prevNodes = new Node[level];
    boolean exist = false; // 记录要删除的节点是否存在
    // 从最高的有效层开始搜索 其索引时 `有效层数 - 1`
    for (int i = level - 1; i >= 0; i--) {
        // 拿到 下标为 i 的那一层的 第一个实际节点 first.nexts[i]
        //  拿这个节点的 key 和 目标Key进行比较
        int compareResult = -1;
        // 如果当前节点不是尾结点  并且（and） 当前节点 key 小于 目标key
        while (node.nexts[i] != null && (compareResult = compare(node.nexts[i].key, key)) < 0) {
            // 则前往当前节点的下一个节点
            node = node.nexts[i];
        }
        // 来到这里，说明当前节点key 大于等于 目标key 了
        // 检查是否是 等于 的情况
        if (compareResult == 0) // 一旦相等，说明要删除的 `key` 存在
            exist = true; // 将标记为设置为 true
        // 返回上个节点，进入下一层
        // 一旦触发了层下降，则记录前驱节点
        prevNodes[i] = node;
        // - 返回上一节点：当前node指向的就是"上一个节点"，所以啥也不用写
        // - 进入下一层，就是 i--：根据for循环，啥也不用写
    }
    // 搜索查找完毕，检查 exist 的值
    // 如果 exist = false ， 说明要删除的 `key` 根本不存在，直接返回
    if (!exist) return null;
    // 否则，确实要删除`key`，此时的 node 就指向了我们要删除节点的 前驱结点
    // 删除目标节点
    // 获取要删除节点的高度
    // 用一个变量记录要被删除的节点
    Node<K, V> deleteNode = node.nexts[0];
    int deleteLevel = deleteNode.nexts.length; // 被删除节点的高度
    // 删除：维护前后节点指针
    for (int i = 0; i < deleteLevel; i++) { // 遍历有效层
        prevNodes[i].nexts[i] = deleteNode.nexts[i];
    }

    size--; // 有效节点数减少
    // 维护跳表的有效层数 level
    int newLevel = level; // 先获取当前有效层数
    while (--newLevel >= 0 && first.nexts[newLevel] == null) {
        // 对于 level 层来说，最高层索引为 level - 1
        // 依然有层可下，在这一层，头节点的 next 直接指向了 尾节点，说明该层无效，将有效层数 - 1
        // level = newLevel;
        level--;
    }

    return deleteNode.value; // 返回被删除节点的value
}

内部节点类

成员变量

变量	含义
`K key`	键
`V value`	值
`Node<K, V>[] nexts`	对于单向链表，每个节点都存储着其下一个节点的引用对于跳表，每个节点都有一个 `节点数组`，存储着所有其对应的所有层的下一个节点的引用

构造方法

有参构造方法

参数	含义	处理方式
`K key`	键	`this.key = key`
`V value`	值	`this.value = value`
`int level`	要创建节点所具有的层数，也即内部节点数组 `nexts` 的数组长度	`this.nexts = new Node[level]`

内部节点类

/**
 * 内部节点
 */
private static class Node<K, V> {
    K key;
    V value;
    Node<K, V>[] nexts;

    // 构造方法
    public Node() {
    }

    /**
     * 有参构造方法
     *
     * @param key   键
     * @param value 值
     * @param level 新节点的层数，也即内部节点数组的数组长度
     */
    public Node(K key, V value, int level) {
        this.key = key;
        this.value = value;
        this.nexts = new Node[level];
    }
}

测试

使用 添加方法 添加若干元素
使用 查找方法 查找一个元素
使用 删除方法 删除上一步查找的元素，再用 查找方法 再次查找，此时应当查不到了

跳表测试

public static void main(String[] args) {
    MySkipList<Integer, Integer> skipList = new MySkipList<>();

    skipList.put(1, 11);
    skipList.put(2, 22);
    skipList.put(3, 33);
    skipList.put(4, 44);

    System.out.println("skipList.get(1) = " + skipList.get(1));

    System.out.println("skipList.remove(1) = " + skipList.remove(1));
    System.out.println("skipList.get(1) = " + skipList.get(1));
}

运行结果

skipList.get(1) = 11
skipList.remove(1) = 11
skipList.get(1) = null

跳表相关特征详解

跳表的层数

跳表是按层构建的，底层是一个普通的有序链表，高层相当于是底层的“快速通道”
在第 i 层中的元素按照某个固定的概率 p （通常为 0.25 或 0.5）出现在第 i+1 层中，产生越高的层数，概率越低
- 元素层数恰好等于 1 的概率为 1 - p
- 元素层数大于等于 2 的概率为 p，而元素层数恰好等于 2 的概率为 p * (1 - p)
- 一个元素的平均层数是 1 / (1 - p)
当 p = 0.5 时，每个元素所包含的平均指针数量是 2
当 p = 0.25 时，每个元素所包含的平均指针数量是 1.33

复杂度分析

每一层的元素数量
- 在第 1 层，即最底层，链表固定有 n 个元素
- 在第 2 层，平均有 n * p 个元素
- 在第 k 层，平均有 n * p^k 个元素
最高层的层数是 log n，以 1 / p 为底，平均有 1 / p 个元素
- 在搜索时，每一层链表预期查找步数最多为 1 / p
- 总查找步数为 -(log n/p) 以 p 为底，时间复杂度为 O(logn)

跳表#

思考

使用跳表优化链表#

跳表的实现#

成员变量#

构造方法#

比较方法#

键判空方法#

查找方法#

随机层数方法#

添加方法#

删除方法#

内部节点类#

成员变量#

构造方法#

测试#

跳表相关特征详解#

跳表的层数#

复杂度分析#

跳表

使用跳表优化链表

跳表的实现

成员变量

构造方法

比较方法

键判空方法

查找方法

随机层数方法

添加方法

删除方法

内部节点类

成员变量

构造方法

测试

跳表相关特征详解

跳表的层数

复杂度分析