跳表-披着链表外衣的伪搜索树

本文参考资源:

【数据结构与算法】之跳表(Java实现)---第九篇Java震哥聊校招-CSDN博客

跳表的原理及实例 - Rogn - 博客园

跳表Java实现Java偏离的定弦-CSDN博客

跳表概述

如果说某一种数据结构能达到以logn的速度查找数据,相信大多数人第一反应都是二分查找或是搜索树。

对于二分查找来说,它通常是一个有序数组,虽然查找效率达到了logn,但插入效率要么就是数组不允许插入,要么就是arraylist为logn。

对于搜索树,则必须要是自平衡的搜索树才能在插入了很多数据之后依然保持logn的查找效率,这就要求插入涉及到旋转平衡操作,实现较复杂。

而我们今天要介绍的主角——跳表,相较于红黑树、AVL等自平衡搜索树的实现会更简单些,查找效率和插入效率也都达到了logn。

跳表的性质

  1. 由很多层结构组成,level是通过一定的概率随机产生的
  2. 每一层都是一个有序的链表,默认是升序
  3. 最底层(Level 1)的链表包含所有元素;
  4. 如果一个元素出现在Level i 的链表中,则它在Level i 之下的链表也都会出现; 
  5. 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

跳表原理

用图片形式来理解跳表:

跳表-披着链表外衣的伪搜索树

如下图,对初始链表做一层“索引”,每两个节点提取一个节点到上一层,然后用down指针连接到下一层。

跳表-披着链表外衣的伪搜索树

现在我们查询16这个节点。从第一级索引开始,找到13,并且下一个为17,显然16在这两个节点之间,利用down指针下降一层,这次我们遍历2次即可。利用索引后,遍历了5+2=7次,而原始链表需要10次,这里加一层索引遍历次数减少了,效率提高了一点,但还不够,我们继续往上添加索引层。

跳表-披着链表外衣的伪搜索树

这里我不再算了,结果是6次,效率又提高了!

那么这种链表加多级索引就是跳表的结构了。可以看出来最后形成的就是一个类似于搜索树的结构。

跳表的操作

Java中已经有了跳表思想的实现:concurrent包下的ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap)和 ConcurrentSkipListSet(在功能上对应HashSet)。

跳表的插入

跳表插入的时间复杂度为:O(logn),支持高效的动态插入。

在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是O(1)。但是为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这个查找的操作就会比较耗时。

对于纯粹的单链表,需要遍历每个结点,来找到插入的位置。但是对于跳表来说,查找的时间复杂度为O(logn),所以这里查找某个数据应该插入的位置的时间复杂度也是O(logn),如下图所示:

跳表-披着链表外衣的伪搜索树

跳表的删除

跳表的删除操作时间复杂度为:O(logn),支持动态的删除。

在跳表中删除某个结点时,如果这个结点在索引中也出现了,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点,然后再通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点(双向链表除外)。因此跳表的删除操作时间复杂度即为O(logn)。

跳表索引动态更新

当我们不断地往跳表中插入数据时,我们如果不更新索引,就有可能出现某2个索引节点之间的数据非常多的情况,在极端情况下,跳表还会退化成单链表,如下图所示:

跳表-披着链表外衣的伪搜索树

作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中的结点多了,索引结点就相应地增加一些,避免复杂度退化,以及查找、插入和删除操作性能的下降。

如果你了解红黑树、AVL树这样的平衡二叉树,你就会知道它们是通过左右旋的方式保持左右子树的大小平衡,而跳表是通过随机函数来维护“平衡性”。

当我们往跳表中插入数据的时候,我们可以通过一个随机函数,来决定这个结点插入到哪几级索引层中,比如随机函数生成了值K,那我们就将这个结点添加到第一级到第K级这个K级索引中。如下图中要插入数据为6,K=2的例子:

跳表-披着链表外衣的伪搜索树

随机函数的选择是非常有讲究的,从概率上讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能的过度退化。至于随机函数的选择,见下面的代码实现过程,而且实现过程并不是重点,掌握思想即可。

跳表的Java实现

// 跳表中存储的是正整数,并且存储的数据是不重复的
public class SkipList {

    private static final int MAX_LEVEL = 16;    // 结点的个数

    private int levelCount = 1;   // 索引的层级数

    private Node head = new Node();    // 头结点

    private Random random = new Random();

    // Node内部类
    public class Node{
        private int data = -1;
        private Node next[] = new Node[MAX_LEVEL];
        private int maxLevel = 0;

        // 重写toString方法
        @Override
        public String toString(){
            StringBuilder builder = new StringBuilder();
            builder.append("{data:");
            builder.append(data);
            builder.append("; leves: ");
            builder.append(maxLevel);
            builder.append(" }");
            return builder.toString();
        }
    }

    // 查找操作
    public Node find(int value){
        Node p = head;
        for(int i = levelCount - 1; i >= 0; --i){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
        }

        if(p.next[0] != null && p.next[0].data == value){
            return p.next[0];    // 找到,则返回原始链表中的结点
        }else{
            return null;
        }
    }

    // 插入操作
    public void insert(int value){
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;   // 通过随机函数改变索引层的结点布置
        Node update[] = new Node[level];
        for(int i = 0; i < level; ++i){
            update[i] = head;
        }

        Node p = head;
        for(int i = level - 1; i >= 0; --i){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            update[i] = p;
        }

        for(int i = 0; i < level; ++i){
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
        if(levelCount < level){
            levelCount = level;
        }
    }

    // 删除操作
    public void delete(int value){
        Node[] update = new Node[levelCount];
        Node p = head;
        for(int i = levelCount - 1; i >= 0; --i){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            update[i] = p;
        }

        if(p.next[0] != null && p.next[0].data == value){
            for(int i = levelCount - 1; i >= 0; --i){
                if(update[i].next[i] != null && update[i].next[i].data == value){
                    update[i].next[i] = update[i].next[i].next[i];
                }
            }
        }
    }

    // 随机函数
    private int randomLevel(){
        int level = 1;
        for(int i = 1; i < MAX_LEVEL; ++i){
            if(random.nextInt() % 2 == 1){
                level++;
            }
        }

        return level;
    }

    // 显示跳表中的结点
    public void display(){
        Node p = head;
        while(p.next[0] != null){
            System.out.println(p.next[0] + " ");
            p = p.next[0];
        }
        System.out.println();
    }

}

跳表的应用

  • Lucene3.0版本之前使用跳表结构存储词典,后来换成了FST(有限状态转移机)
  • Redis在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构。
  • ……

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e8%b7%b3%e8%a1%a8-%e6%8a%ab%e7%9d%80%e9%93%be%e8%a1%a8%e5%a4%96%e8%a1%a3%e7%9a%84%e4%bc%aa%e6%90%9c%e7%b4%a2%e6%a0%91/

发表评论

电子邮件地址不会被公开。