跳跃表的原理和实现（Java）

一、高效查找算法

我们在实际开发中经常会有在一堆数据中查找一个指定数据的需求，而常用的支持高效查找算法的实现方式有以下几种：

  1. 有序数组：这种方式的存储结构，优点是支持数据的随机访问，并且可以采用二分查找算法降低查找操作的复杂度。缺点同样很明显，插入和删除数据时，为了保持元素的有序性，需要进行大量的移动数据的操作。
  2. 二叉查找树：如果需要一个既支持高效的二分查找算法，又能快速的进行插入和删除操作的数据结构，那首先就是二叉查找树莫属了。缺点是在某些极端情况下，二叉查找树有可能变成一个线性链表。
  3. 平衡二叉树：二叉树表示不服，于是基于二叉查找树的优点，对其缺点进行改进，引入了平衡的概念。根据平衡算法的不同，具体实现有AVL树、B树（B-Tree）、B+树（B+Tree）、红黑树 等等。但是平衡二叉树的实现多数比较复杂，较难理解。
  4. 跳跃表：同样支持对数据进行高效的查找，插入和删除数据操作也比较简单，最重要的就是实现比较平衡二叉树真是轻量几个数量级。缺点就是存在一定数据冗余。

二、跳跃表

跳跃表（SkipList）是一种可以替代平衡树的数据结构。跳跃表让已排序的数据分布在多层次的链表结构中，默认是将 Key 值升序排列的，以 0-1 的随机值决定一个数据是否能够攀升到高层次的链表中。它通过容许一定的数据冗余，达到 “以空间换时间” 的目的。

跳跃表的效率和 AVL 相媲美，查找、添加、插入、删除操作都能够在 O(LogN) 的复杂度内完成。讲了那么多，下面就直接进入主题，详细的看一看跳跃表是怎么实现的。

三、跳跃表的实现

上面这张图就是一个跳跃表的实例，先说一下跳跃表的构造特征：

  • 一个跳跃表应该有若干个层（Level）链表组成；
  • 跳跃表中最底层的链表包含所有数据； 每一层链表中的数据都是有序的；
  • 如果一个元素 X 出现在第i层，那么编号比 i 小的层都包含元素 X；
  • 第 i 层的元素通过一个指针指向下一层拥有相同值的元素；
  • 在每一层中，-∞ 和 +∞ 两个元素都出现(分别表示 INT_MIN 和 INT_MAX)；
  • 头指针（head）指向最高一层的第一个元素；

1、定义链表中节点的模型

image.png

Java 代码实现如下：

public class SkipListEntry<T> {
    // data
    public Integer key;
    public T value;

    // links
    public SkipListEntry up;
    public SkipListEntry down;
    public SkipListEntry left;
    public SkipListEntry right;

    // constructor
    public SkipListEntry(Integer key, T value) {
        this.key = key;
        this.value = value;
    }
    
    // methods...
}

可以看到节点模型主要分为2个部分。

data 部分包含具体的存储数据，这里为了不引入其他杂乱的问题，使用 Integer 作为 key 的类型，Object 作为value 的类型。

links 部分包含4个指针，分别是 up、down、left、right，单从名字上就能够明白它们的作用。

2、跳跃表本身的模型

public class SkipList {
    // 节点数量
    public int n;
    // 节点最大层数
    public int h;
    
    // 第一个节点
    SkipListEntry head;
    // 最后一个节点
    SkipListEntry tail;
    
    public Random r;
}

Note: Random 类的实例对象 r 用来决定新添加的节点是否能够向更高一层的链表攀升。

3、初始化跳跃表的实例

构造函数将初始化一个空的跳跃表看起来像下面这样：


image.png

构造函数的 Java 代码：

public SkipList() {
    // 创建 head 节点
    this.head = new SkipListEntry(Integer.MIN_VALUE, null);
    // 创建 tail 节点
    this.tail = new SkipListEntry(Integer.MAX_VALUE, null);

    // 将 head 节点的右指针指向 tail 节点
    this.head.right = tail;
    // 将 tail 节点的左指针指向 head 节点
    this.tail.left = head;

    this.h = 0;
    this.n = 0;
    this.r = new Random();
}

4、基本操作

跳跃表需要实现查找、插入、移除这些基本操作：

  • get(Integer key) ： 根据 key 值查找某个元素
  • put(Integer key, Object value) ：插入一个新的元素，元素已存在时为修改操作
  • remove(Integer key)： 根据 key 值删除某个元素

虽然看似是 3 个不同的操作，但是究其本质，要实现这 3 个操作，都得先找到某个元素或是定位到一个元素，好在下一个位子插入新元素。那么，我们就先把这个 findEntry 的方法实现吧。

image.png

上面的图示使用紫色的箭头画出了在一个 SkipList 中查找 key 值 50 的过程。简述如下：

  1. 从 head 出发，因为 head 指向最顶层（top level）链表的开始节点，相当于从顶层开始查找；
  2. 移动到当前节点的右指针（right）指向的节点，直到右节点的 key 值大于要查找的 key 值时停止；
  3. 如果还有更低层次的链表，则移动到当前节点的下一层节点（down），如果已经处于最底层，则退出；

重复第 2 步和第 3 步，直到查找到 key 值所在的节点，或者不存在而退出查找；

Java 代码实现如下：

private SkipListEntry findEntry(Integer key) {
    // 从head头节点开始查找
    SkipListEntry p = head;

    while (true) {
        // 从左向右查找，直到右节点的key值大于要查找的key值
        while (p.right.key <= key) {
            p = p.right;
        }

        // 如果有更低层的节点，则向低层移动
        if (p.down != null) {
            p = p.down;
        } else {
            break;
        }
    }

    // 返回p，！注意这里p的key值是小于等于传入key的值的（p.key <= key）
    return p;
}

注意以下几点：

  1. 如果传入的 key 值在跳跃表中存在，则 findEntry 返回该对象的底层节点；

  2. 如果传入的 key 值在跳跃表中不存在，则 findEntry 返回跳跃表中 key 值小于 key，并且 key 值相差最小的底层节点；

示例，在跳跃表中查找 key＝42 的元素节点，将返回 key＝39 的节点。如下图所示：


image.png

基于 findEntry 方法，我们就能很容易的实现前面所说的一些操作了。

get方法

public Object get(Integer key) {
    SkipListEntry p = findEntry(key);

    if (p.key.equals(key)) {
        return p.value;
    } else {
        return null;
    }
}

put方法

一些需要注意的步骤：

  1. 如果 put 的 key 值在跳跃表中存在，则进行修改操作；
  2. 如果 put 的 key 值在跳跃表中不存在，则需要进行新增节点的操作，并且需要由 random 随机数决定新加入的节点的高度（最大level）；
  3. 当新添加的节点高度达到跳跃表的最大 level，需要添加一个空白层（除了-oo 和 +oo 没有别的节点）

下面我们一步一步的通过图示看一下插入节点的过程：

第一步，查找适合插入的位子

第二步，在查找到的p节点后面插入新增的节点q

image.png

第三步，重复下面的操作，使用随机数决定新增节点的高度

  1. 从p节点开始，向左移动，直到找到含有更高level节点的节点；
  2. 将p指针向上移动一个level；
  3. 创建一个和q节点data一样的节点，插入位子在跳跃表中p的右方和q的上方；
  4. 直到随机数不满足向上攀升的条件为止；

图示如下：

只要随机数满足条件，key＝42 的节点就会一直向上攀升，直到它的 level 等于跳跃表的高度（height）。这个时候我们需要在跳跃表的最顶层添加一个空白层，同时跳跃表的 height＋1，以满足下一次新增节点的操作。

Java代码实现如下：

public Object put(Integer key, Object value) {

    SkipListEntry p, q;
    int i = 0;

    // 查找适合插入的位子
    p = findEntry(key);

    // 如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
    if (p.key.equals(key)) {
        Object oldValue = p.value;
        p.value = value;
        return oldValue;
    }

    // 如果跳跃表中不存在含有key值的节点，则进行新增操作
    q = new SkipListEntry(key, value);
    q.left = p;
    q.right = p.right;
    p.right.left = q;
    p.right = q;

    // 再使用随机数决定是否要向更高level攀升
    while (r.nextDouble() < 0.5) {

        // 如果新元素的级别已经达到跳跃表的最大高度，则新建空白层
        if (i >= h) {
            addEmptyLevel();
        }

        // 从p向左扫描含有高层节点的节点
        while (p.up == null) {
            p = p.left;
        }
        p = p.up;

        // 新增和q指针指向的节点含有相同key值的节点对象
        // 这里需要注意的是除底层节点之外的节点对象是不需要value值的
        SkipListEntry z = new SkipListEntry(key, null);

        z.left = p;
        z.right = p.right;
        p.right.left = z;
        p.right = z;

        z.down = q;
        q.up = z;

        q = z;
        i = i + 1;
    }

    n = n + 1;

    // 返回null，没有旧节点的value值
    return null;
}

remove方法

删除节点的操作相对 put 就比较简单了，首先查找到包含 key 值的节点，将节点从链表中移除，接着如果有更高 level 的节点，则 repeat 这个操作即可。
Java代码实现如下：

public Object remove(Integer key) {
    SkipListEntry p, q;

    p = findEntry(key);

    if (!p.key.equals(key)) {
        return null;
    }

    Object oldValue = p.value;
    while (p != null) {
        q = p.up;
        p.left.right = p.right;
        p.right.left = p.left;
        p = q;
    }
    return oldValue;
}

跳跃表的原理和实现到这里就结束了。

还有需要说明的一点是：跳跃表每次运行的结果是不一样的，这就是为什么说跳跃表是属于随机化数据结构。（Random的存在导致的）

四、跳跃表在Java中的应用

  • ConcurrentSkipListMap：在功能上对应HashTable、HashMap、TreeMap；
  • ConcurrentSkipListSet ： 在功能上对应HashSet；

确切的说，SkipList 更像 Java 中的 TreeMap ，TreeMap 基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到 O(log n)。

HashMap 是基于散列表实现的，查找时间复杂度平均能达到 O(1)。ConcurrentSkipListMap 是基于跳跃表实现的，查找时间复杂度平均能达到 O(log n)。

ConcurrentSkipListMap 具有 SkipList 的性质 ，并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。

TreeMap 插入数据时平衡树采用严格的旋转操作（比如平衡二叉树有左旋右旋）来保证平衡，因此 SkipList 比较容易实现，而且相比平衡树有着较高的运行效率。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 201,924评论 5赞 474
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,781评论 2赞 378
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 148,813评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,264评论 1赞 272
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,273评论 5赞 363
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,383评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,800评论 3赞 393
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,482评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,673评论 1赞 295
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,497评论 2赞 318
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,545评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,240评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,802评论 3赞 304
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,866评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,101评论 1赞 258
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,673评论 2赞 348
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,245评论 2赞 341