22、数据结构与算法进阶:跳表

摘要
跳表可以降低有序链表的添加、删除和搜索的平均时间复杂度。跳表的应用场景也是比较多,比如在 Redis 中使用。它的实现逻辑也是值得去学习的。

一个有序链表的搜索、添加和删除的平均时间复杂度为 O(n)。那么,是否可以利用二分搜索法优化有序链表,使得有序链表的搜索、添加和删除的平均时间复杂度降低为 O(logn)?

我们知道,数组是可以高效的随机访问的,因为数组是存在索引的。但是链表不具备索引,所以不能像有序数组那样直接使用二分搜优化。那么有什么其他方法可以让有序数组的搜索、添加和删除的平均时间复杂度为 O(logn) 呢?

答案是一定存在的,那就是跳表!!!

什么是跳表?

跳表也被称为跳跃表,或者跳跃列表,就是在有序链表的基础上增加了“跳跃”的功能。它是由 William Pugh 在 1990 年发布的,设计的初衷是为了取代平衡树(比如红黑树)。

著名的Key-Value 数据库,比如 Redis 和 LevelDB。Redis 中的 SortedSet,LevelDB 中的 MemTable 都用到了跳表。

跳表相对于平衡树,跳表的实现和维护会更加简单。跳表的搜索、删除和添加的平均时间复杂度是 O(logn),如下图(图片来自网络)。
*

搜索

在跳表中搜索时,按照以下步骤进行:

1、 从顶层链表的首元素开始,从左到右搜索,直至找到一个大于或等于目标的元素,或者到达当前层链表的尾部;
2、 如果该元素等于目标元素,则表明该元素已被找到;
3、 如果该元素大于目标元素或者已到达链表的尾部,则退回到当前层的前一个元素,然后转入下一层进行搜索;

添加和删除

跳表中添加元素时,随机确定新添加元素的层数。删除元素时,整个跳表的层数也可能会降低。

层数

跳表是按照层构建的,底层是一个普通的有序链表,高层相当于是低层的“快速通道”。

假设在第 i 层出现的元素 x,在第 i+1 层出现 x 的固定概率为 p,那么,产出越高的层数,概率就越低了,比如:

  • 元素层数恰好等于 1 的概率为 1-p;
  • 元素层数大于等于 2 的概率为 p,而元素层数恰好等于 2 的概率为 p*(1-p);
  • 元素层数大于等于 3 的概率为 p^2,而元素层数恰好等于 3 的概率为 p^2 * (1-p);
  • 元素层数大于等于 4 的概率为 p^3,而元素层数恰好等于 4 的概率为 p^3 * (1-p);

以此类推,一个元素的平均层数是 1 / (1 - p)。通常 p 的值设置为 1/2 或者 1/4,所以每个元素所包含的平均指针数量是 2 或者 1.33。

实现代码

先创建一个类,在类中定义一些属性,并实现一些简单的函数:

public class SkipList<K, V> {
   
     
    // 最大层数
    private static final int MAX_LEVEL = 32;
    // 概率值
    private static final double p = 0.5;
    // 元素数量
    private int size;
    // 比较函数
    private Comparator<K> comparator;
    // 有效层数
    private int level;
    // 不存放任何 K-V
    private Node<K, V> first;

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

    public SkipList() {
   
     
        this(null);
    }

    public int size() {
   
     
        return size;
    }

    public boolean isEmpty() {
   
     
        return size == 0;
    }
}

comparator 属性定义时需要引入 java.util.Comparator 系统工具类。

SkipList 类的构造函数中,可以看到 Node 类的创建需要传入 3 个参数,其中一个是传递层数,因为 Node 中需要定义一个数组来存放指向不同层的指针:

private static class Node<K, V> {
   
     
    K key;
    V value;
    Node<K, V>[] nexts;
    public Node(K key, V value, int level) {
   
     
        super();
        this.key = key;
        this.value = value;
        this.nexts = new Node[level];
    }
}

添加元素

接下来实现添加元素函数,在实现过程中要这几步走:

1、 从顶层开始,遍历每一层,找到要添加元素的所有前驱节点,如果出现添加的元素和跳表中的元素相同,那么就替换它,结束;
2、 对新添加的元素创建一个新的节点,随机一个层数,然后遍历新的层数,将新的节点添加进去;
3、 size加一,重新确定跳表的层高;

public V put(K key, V value) {
   
     
    keyCheck(key);

    Node<K, V> node = first;
    Node<K, V>[] prevs = new Node[level];
    for (int i = level - 1; i >= 0; i--) {
   
     
        int cmp = -1;
        while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
   
     
            node = node.nexts[i];
        }

        if (cmp == 0) {
   
      // 节点存在
            V oldV = node.nexts[i].value;
            node.nexts[i].value = value;
            return oldV;
        }
        prevs[i] = node;
    }

    // 新节点的层数
    int newLevel = randomLevel();
    // 添加新节点
    Node<K, V> newNode = new Node<>(key, value, newLevel); 
    // 设置前驱和后继
    for (int i = 0; i < newLevel; i++) {
   
     
        if (i >= level) {
   
     
            first.nexts[i] = newNode;
        } else {
   
     
            newNode.nexts[i] = prevs[i].nexts[i];
            prevs[i].nexts[i] = newNode;
        }
    }
    // 节点数量增加
    size++;
    // 计算跳表的最终层数
    level = Math.max(level, newLevel);
    return null;
}

随机层数的函数需要 pMAX_LEVEL 一起来确定:

private int randomLevel() {
   
     
    int level = 1;
    while (Math.random() < p && level < MAX_LEVEL) {
   
     
        level ++;
    }
    return level;
}

搜索元素

搜索元素就简单很多了,就是一层层的遍历,每一层都从头遍历到尾部,直至找到元素或者全部遍历完:

public V get(K key) {
   
     
    keyCheck(key);
    Node<K, V> node = first;
    for (int i = level-1; i >= 0; i--) {
   
     
        int cmp = -1;
        while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
   
     
            node = node.nexts[i];
        }

        if (cmp == 0) return node.nexts[i].value;
    }
    return null;
}

删除元素

删除元素和添加元素的第一步比较相似,需要多留意不同的地方:

1、 从高层到低层,从头到尾,依次遍历,获取要删除元素的前驱节点,并有个标识,来确定是否存在要删除的元素;
2、 删除节点,也就是要删除的节点的前驱节点指向要删除节点的后继,层与层之间要对应好;
3、 更新层数,如果first节点直接指向null,那么就可以删除该层了;

public V remove(K key) {
   
     
    keyCheck(key);
    Node<K, V> node = first;
    Node<K, V>[] prevs = new Node[level];
    boolean exist = false;
    for (int i = level-1; i >= 0; i--) {
   
     
        int cmp = -1;
        while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
   
     
            node = node.nexts[i];
        }
        prevs[i] = node;
        if (cmp == 0) exist = true;
    }

    if (!exist) return null;

    // 需要被删除的节点
    Node<K, V> removeNode = node.nexts[0];

    // 设置前驱和后继 ???
    for (int i = 0; i < removeNode.nexts.length; i++) {
   
     

        prevs[i].nexts[i] = removeNode.nexts[i];
    }

    // 更新跳表的层数
    int newLevel = level;
    while (--newLevel >= 0 && first.nexts[newLevel] == null) {
   
     
        level = newLevel;
    }

    // 数量减1
    size--;

    return removeNode.value;
}

为什么 Node<K, V> removeNode = node.nexts[0]; 就是要删除的节点?

因为跳表的最底层就是一个包含所以节点的有序链表,添加元素也是从底层开始的,node 已经是要删除节点的前驱节点了, nexts[0] 就是最底层的节点,必然指向要删除的节点。

总结

  • 跳表可以让添加、删除和搜索的平均时间复杂度降低为 O(logn);
  • 跳表是二分法的思维实现;
  • 跳表更改前驱和后继是添加和删除函数的重点。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: