数据结构基础06——线性数据结构之跳表

增加了向前指针(或者叫向下指针)的链表叫作跳表。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

实现场景

如果我们给有一个有序的链表,需要找到属性值为x的节点。 因为链表自身的特性,每次查找都需要一次遍历O(n)。现在我们需要对它进行优化来提高查找效率,在保持原有链表不变的情况下(如:不把链表变成数组通过散列映射,见散列表)有哪些优化方法呢?

其中一个比较好的办法就是跳表(就是比较废内存...)

在说跳表之前首先需要说的是二分查找。

猜数字游戏(应该都写过吧~):给定1 - 100中的随机一个数x,玩家猜一个数字,告诉你大了还是小了或者猜到了。问需要猜几次?每次我们取其中一半,逐渐缩小。如:50,25,12...对于n个数字,猜到的时间复杂度为O(logn)非常高效。

同理,如果我们在链表中找数字x前,先看x/2节点的值是大还是小,再向前遍历不就可以了吗?当然当我们在x/2节点过程中不能用遍历。
时间不够空间来凑。我们只需要在原有的链表基础上创建一个新的节点对象Node_m,其中 Node_m 包含中间节点的引用(其实是随机出的节点)和排序的分值。每次通过 Node_m 去找到对应的中间节点即可,然后判断大了还是小了进行向前或者向后查找(如果是单链表,就是从头开始,还是从中间开始向后查找)。就可以了

继续优化
如果我们要找的数字刚好在这个链表在前半部分或者最后。如:1 - 10亿,而我们要找的数字刚好是4_9999_9999。不还是从头开始遍历吗?这个时候,我们就可以考虑拆分粒度。二分查找可以变成三查找,四分查找,五分查找..X分查找(其实是概率函数)。
这样我们需要的外部节点就不是只有 Node_m 一个节点了,而是x个节点组成的集合,我们将这m个节点组成一个新的线性表。就相当于在原来的链表上面再加一层链表(索引),链表中的每一个节点都额外加指向原始链表的引用:

image.png

继续优化
如果原始链表的大小实在太大,如:10亿数据,我们上层的索引平均对应每100个一个节点,那么索引也要1千万个节点。遍历1千万节点的链表也需要一定的时间,有没有什么更快的办法呢?很简单,这就回到了我们最初问题的递归。有没有什么办法可以让一个链表查找速度更快呢?有加一层索引~

image.png

image.png

上述这种链表加多级索引的结构就称之为——跳表了。

插入和删除

跳表的查询操作实际上,如上所示。而且跳表的插入、删除操作的时间复杂度也是 O(logn)!

在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是 O(1)。但是,这里为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这时就需要遍历O(n)来找到要插入位置。但是,对于跳表来说,查找的复杂度是 O(logn),所以这里查找某个数据应该插入的位置,方法也是类似的,时间复杂度也是 O(logn)。如下:
image.png

再来看删除操作。
如果删除的这个结点在索引中也有出现,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点,然后通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点。当然,如果我们用的是双向链表,就不需要考虑这个问题了。

索引的更新

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

image.png

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

这里可以通过随机函数来维护前面提到的“平衡性”。当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢?我们通过一个随机函数,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

也就是前面我们所谓的“n分查找”,不是基于一半或者多少个而是随机函数。

image.png

随机函数的选择很有讲究,从概率上来讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能过度退化。至于随机函数的选择,感兴趣的话,可以去了解Redis 中关于有序集合的跳表实现。

import java.util.Random;

/**
 * 1,跳表的一种实现方法,用于练习。跳表中存储的是正整数,并且存储的是不重复的。
 * 2,本类是参考作者zheng ,自己学习,优化了添加方法
 * 3,看完这个,我觉得再看ConcurrentSkipListMap 源码,会有很大收获
 * Author:ldb
 */
public class SkipList2 {

    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;

    /**
     * 带头链表
     */
    private Node head = new Node(MAX_LEVEL);
    private Random r = new Random();

    public Node find(int value) {
        Node p = head;
        // 从最大层开始查找,找到前一节点,通过--i,移动到下层再开始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一节点
                p = p.forwards[i];
            }
        }

        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        } else {
            return null;
        }
    }

    /**
     * 优化了作者zheng的插入方法
     *
     * @param value 值
     */
    public void insert(int value) {
        int level = head.forwards[0] == null ? 1 : randomLevel();
        // 每次只增加一层,如果条件满足
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node update[] = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        Node p = head;
        // 从最大层开始查找,找到前一节点,通过--i,移动到下层再开始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一节点
                p = p.forwards[i];
            }
            // levelCount 会 > level,所以加上判断
            if (level > i) {
                update[i] = p;
            }

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

    }

    /**
     * 优化了作者zheng的插入方法2
     *
     * @param value 值
     */
    public void insert2(int value) {
        int level = head.forwards[0] == null ? 1 : randomLevel();
        // 每次只增加一层,如果条件满足
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node p = head;
        // 从最大层开始查找,找到前一节点,通过--i,移动到下层再开始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一节点
                p = p.forwards[i];
            }
            // levelCount 会 > level,所以加上判断
            if (level > i) {
                if (p.forwards[i] == null) {
                    p.forwards[i] = newNode;
                } else {
                    Node next = p.forwards[i];
                    p.forwards[i] = newNode;
                    newNode.forwards[i] = next;
                }
            }

        }

    }

    /**
     * 作者zheng的插入方法,未优化前,优化后参见上面insert()
     *
     * @param value
     * @param level 0 表示随机层数,不为0,表示指定层数,指定层数
     *              可以让每次打印结果不变动,这里是为了便于学习理解
     */
    public void insert(int value, int level) {
        // 随机一个层数
        if (level == 0) {
            level = randomLevel();
        }
        // 创建新节点
        Node newNode = new Node(level);
        newNode.data = value;
        // 表示从最大层到低层,都要有节点数据
        newNode.maxLevel = level;
        // 记录要更新的层数,表示新节点要更新到哪几层
        Node update[] = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        /**
         *
         * 1,说明:层是从下到上的,这里最下层编号是0,最上层编号是15
         * 2,这里没有从已有数据最大层(编号最大)开始找,(而是随机层的最大层)导致有些问题。
         *    如果数据量为1亿,随机level=1 ,那么插入时间复杂度为O(n)
         */
        Node p = head;
        for (int i = level - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            // 这里update[i]表示当前层节点的前一节点,因为要找到前一节点,才好插入数据
            update[i] = p;
        }

        // 将每一层节点和后面节点关联
        for (int i = 0; i < level; ++i) {
            // 记录当前层节点后面节点指针
            newNode.forwards[i] = update[i].forwards[i];
            // 前一个节点的指针,指向当前节点
            update[i].forwards[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.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            update[i] = p;
        }

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

    /**
     * 随机 level 次,如果是奇数层数 +1,防止伪随机
     *
     * @return
     */
    private int randomLevel() {
        int level = 1;
        for (int i = 1; i < MAX_LEVEL; ++i) {
            if (r.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    /**
     * 打印每个节点数据和最大层数
     */
    public void printAll() {
        Node p = head;
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }

    /**
     * 打印所有数据
     */
    public void printAll_beautiful() {
        Node p = head;
        Node[] c = p.forwards;
        Node[] d = c;
        int maxLevel = c.length;
        for (int i = maxLevel - 1; i >= 0; i--) {
            do {
                System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
            } while (d[i] != null && (d = d[i].forwards)[i] != null);
            System.out.println();
            d = c;
        }
    }

    /**
     * 跳表的节点,每个节点记录了当前节点数据和所在层数数据
     */
    public class Node {
        private int data = -1;
        /**
         * 表示当前节点位置的下一个节点所有层的数据,从上层切换到下层,就是数组下标-1,
         * forwards[3]表示当前节点在第三层的下一个节点。
         */
        private Node forwards[];

        /**
         * 这个值其实可以不用,看优化insert()
         */
        private int maxLevel = 0;

        public Node(int level) {
            forwards = new Node[level];
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");
            return builder.toString();
        }
    }

}
更新时间:2020-01-26 20:37:27

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础06线性数据结构之跳表
最后更新:2020-01-26 20:37:27

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×