跳表

跳表【转载】

原文:https://www.jianshu.com/p/8d2e808e8860

---

跳表 = 链表 + 多级索引

跳表使用空间换时间的设计思路，通过构造多级索引来提高查询的效率，实现了基于链表的 二分查找。跳表是一种动态数据结构，支持快读的插入，删除，查找操作，时间复杂度都是 O（lng）

跳表跳表的空间复杂是 O(n)。跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。跳表的代码比起红黑树来说，要简单，易读。

链表加多级索引的结构，就是跳表

对于一个单链表，即便链表中存储的数据是有序的，如果要查询某个数据，也只能从头到尾遍历，时间复杂度 O(n)

image

对于链表建立一级索引，没两个结点提取一个结点到上一级，把抽出来的那一级叫做索引或索引层。图中的 down 表示 down 指针，指向下一级结点

image

这样就可以先在索引层遍历，然后通过索引层结点的 down指针，下降到原始链表这一层，继续遍历

比如要查找16，当在索引层遍历到13时，发现索引层下一个节点是17大于目标16，则可从13的down指针下降到原始链表继续遍历。这样只需要再遍历2个结点，就可以找到值等于16的这个结点了。原来查找16，需要遍历10个结点，加入一层索引后只需要遍历7个结点

加上一层索引之后，查找一个结点需要遍历的结点减少了，查找的效率提高了。继续加再加一级索引，在第一级索引的基础之上，每两个结点就抽出一个结点到第二级索引。现在再查找16，只需要遍历6个结点了，需要遍历的结点树又减少了。

image

下图是一个包含64个结点的链表，建立五级索引

image

在五级索引的作用下，查找62只需要遍历11个结点。当链表的长度n比较大时，比如1000，10000的时候，在构建多级索引之后，查找效率的提升就会非常明显。

跳表的时间复杂度

一个链表里有n个结点，每两个结点会抽出一个结点作为上一级索引的结点，那第一个索引的结点个数大约就是 n / 2 ，第二个索引的结点个数大约就是 n / 4，第三个索引的结点个数大约就是 n / 8。以此类推，也就是说，第K级索引的结点个数就是第 k - 1 级索引的结点个数的 1 / 2,那第 k 级索引结点的个数就是 n / (2 ^ k)

假设索引有 h 级，最高级的索引有2个几点，则 n(2^h) = 2,即 h = logn -1。加上原始链表这一层，整个跳表的高度就是 logn。在跳表中查询某个数据的额时候，如果每一层都要遍历m个结点，那在跳表中查询一个数据的时间复杂度就是 O(m * logn)

按照每两个结点提取一个节点到上一级建立索引这种数据结构，每一级索引都最多只需要遍历3个结点，那么m = 3

假设要查找的数据是x，在第k级索引中遍历到y结点之后，发现x大于y，小于后面的结点z，所以通过y的dom指针，从第k级索引下降到k-1级索引。在第k-1级索引中，y和z之间只有3个结点(包含y和z)所以在k-1级索引中最多只需要遍历3个结点，以此类推，每一级索引都最多只需要遍历3个结点。

image

所以在跳表中查询任意数据的时间复杂度就是 O(logn)

跳表的空间复杂度分析

假设原始链表大小为n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4个结点，以此类推，没上升一级就减少一半，直到剩下2个结点。每层索引的节点数为：
n / 2, n / 4, n / 8, ..., 8, 4, 2
这几级索引的结点总和就是 n / 2 + n / 4 + n / 8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空间复杂度是O(n)

将包含n个结点的单链表构造成跳表，需要额外再接近n个结点的存储空间

如果每三个结点或五个结点，抽一个结点到上级索引

image

那么第一级索引需要大约 n/3 个结点，第二级索引需要大约n / 9个结点。每往上一级，索引结点个数都除以3。为了方便计算，假设最高一级的索引结点个数是1。每3个结点抽一个，每层索引的结点数为：

n / 3, n / 9, n / 27, ..., 9, 3, 1
总的索引结点个数为n / 3 + n / 9 + n / 27 + ...+ 9 + 3 + 1 = n / 2。空间复杂度依然是O(n)，但比每两个结点抽一个结点的索引构建方法，减少了一半的索引结点存储空间。

再实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

跳表动态的插入和删除

跳表插入、删除操作的时间复杂度是O(logn)。

image

对于删除操作，如果这个结点在索引中也有出现，删除原始链表中的结点之后还要删除对应的索引。

查找要删除的结点的时候，一定要获取前驱结点。（双向链表不需要考虑这个问题）

跳表索引动态更新

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

image

作为一种动态数据结构，需要某种手段来维护索引与原始链表大小之间的平衡：

如果链表中的结点多了，索引结点就相应地增加一些，避免复杂退化，以及查找，插入，删除操作的性能下降。

往跳表中插入数据的时候，可以同时将这个数据插入到部分索引层中。通过一个随机函数，来决定将这个终结插入到哪几级索引中，比如随机函数生成了值k，就将这个结点添加到第一级到第k级索引中

image

Redis 用跳表实现有序集合

Redis 中的有序集合是通过跳表来实现的，严格点说，其实还用了散列表。

Redis中的有序集合支持的核心操作主要有：

• 插入一个数据
• 删除一个数据
• 查找一个数据
• 按照区间查找数据；
• 迭代输出有序序列

其中，插入，删除，查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表一样的。但是，按区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后再原始链表中顺序往后遍历就可以了，这样非常高效

跳表相对红黑树而言代码更容易实现，简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗

跳表的简易代码实现

    public class SkipList {
        
        private static final float SKIPLIST_P = 0.5f;
        private static final int MAX_LEVEL = 16;

        private int leveCount = 1;

        private Node cls = new Node();   // 带头链表

        public Node find(int value) {
            Node p = cls;
            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
            }
        }

        // 插入
        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] = cls;
            }

            // record every level largest value which smaller than insert value in update[]
            Node p = cls;
            for(int i = level - 1; i >= 0; --i) {
                while (p.forwards[i] != null && p.forwards[i].data < value) {
                    p = p.forwards[i];
                }
                update[i] = p;// use update save node in search path
            }

            // 搜索路径中的节点下一个节点成为新节点forwords(next)
            for (int i = 0; i < level; ++i) {
                newNode.forwards[i] = update[i].forwards[i];
                update[i].forwards[i] = newNode;
            }

            // update node hight
            if (levelCount < level) levelCount = level;
        }

        // 删除
        public void delete(int value) {
            Node[] update = new Node[levelCount];
            Node p = cls;
            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];
                    }
                }
            }

            while (levelCount>1&&cls.forwards[levelCount]==null) {
                levelCount--;
            }
        }

        // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
        // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
        // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
        //        50%的概率返回 1
        //        25%的概率返回 2
        //      12.5%的概率返回 3 ...

        private int randomLevel() {
            int level = 1;

             while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
             level += 1;
             return level;
        }

        public void printAll() {
            Node p = cls;
            while (p.forwards[0] != null) {
                System.out.print(p.forwards[0] + " ");
                p = p.forwards[0];
            }

            System.out.println();   
        }

        public class Node {
            private int date = -1;
            private Node forwards[] = new Node[MAX_LEVEL];
            private int maxLevel = 0;

             @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();
             }
        }
    }

---

以上