Life is the art of drawing without an eraser.Obstacles are those frightful things you see when you take your eyes off your goal. 生活是一门没有橡皮擦的绘画艺术。当你看到众多困难的时候，通常是你忘记目标的时候。

本文主要分享了一种各方面都十分优秀的动态数据结构---跳表。实现不是目的，重要的是了解它的实现原理和思想，开拓自己的视野。所有源码均已上传至github：

定义

跳表是快速查询一个有序连续元素的数据链表。它虽然是链表，但是它集数组和链表与之所长，跳表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)，非常高效。当然有利就有弊，相对而言，它因为建立了多级索引，因此非常耗内存（O(n)）。它的查找借鉴了二分查找。利用空间换时间，根据随机数建立多级索引。

总结来讲 跳表 = 链表 + 多级索引

举例

 比如有一个链表存了1-100个正整数，我想快速找到67，首先建立一级索引，取中间值50，这样他的一级索引为{1,50,100}，这样可以确定67在50-100之间，但是这样还是不好查找，所以再建立二级索引{1,25,50,75,100}，，，就这样以此类推，不断地建立索引，缩小查找范围，可以快速定位。

redis的有序集合也用到了跳表。

呢为什么Redis用跳表而不是红黑树呢？

答：首先Redis的有序集合有插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。并且跳表的代码更容易实现，可读性高，它不像红黑树那么复杂，它更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

实现

跳表结构

这里，默认-1 数据不存在，maxLevel为0级，forwards为多级索引,并且重写了它的toString方法，为了便于测试，查看日志

public class SNode {        private int data = -1;        private SNode[] forwards = new SNode[MAX_LEVEL];        private int maxLevel = 0;        @Override        public String toString() {            return "{data:" + data + ",level:" + maxLevel + "}";        }    }复制代码

该用法随机了level次，主要是用来防止伪随机的，当随机出奇数的时候，level+1，通过该方法几乎可以达到均匀分布的目的。

private int randomLevel() {        int level = 1;        for (int i = 1; i < MAX_LEVEL; i++) {            if (random.nextInt() % 2 == 1) {                ++level;            }        }//        System.out.println("randomLevel-level = " + level);        return level;    }复制代码

插入

跳表关键在于插入，理解了插入方法的实现，删除和查找即一通百通。

第一个循环比较好理解，构建索引

第二个for循环，根据level倒序遍历，查找头链表的多级索引中满足索引中的值小于插入的值的节点，更新多级索引

第三个for循环更新头链表的多级索引。

over

private void insert(int data) {        int level = randomLevel();        SNode sNode = new SNode();        sNode.data = data;        sNode.maxLevel = level;        SNode[] forwards = new SNode[level];        for (int i = 0; i < level; i++) {            forwards[i] = head;        }        SNode p = head;        for (int i = level - 1; i >= 0; --i) {            while (null != p.forwards[i] && p.forwards[i].data < data) {                p = p.forwards[i];            }            forwards[i] = p;        }        for (int i = 0; i < level; i++) {            sNode.forwards[i] = forwards[i].forwards[i];            forwards[i].forwards[i] = sNode;        }        if (levelCount < level)            levelCount = level;    }复制代码

删除

删除的第一个for循环和新增的呢个循环作用是一样的

第二个循环类似链表的常规删除 node.next = node.next.next

private void delete(int data) {        SNode[] forwards = new SNode[levelCount];        SNode sNode = head;        for (int i = levelCount - 1; i >= 0; --i) {            while (null != sNode.forwards[i] && sNode.forwards[i].data < data) {                sNode = sNode.forwards[i];            }            forwards[i] = sNode;        }        if (null != sNode.forwards[0] && sNode.forwards[0].data == data) {            for (int i = levelCount - 1; i >= 0; --i) {                if (null != forwards[i].forwards[i] && forwards[i].forwards[i].data == data)                    forwards[i].forwards[i] = forwards[i].forwards[i].forwards[i];            }        }    }复制代码

查找

该方法是倒序遍历多级索引，不断缩小范围，查找到相对应的索引等级，然后找

forwards[0].data == data即可

private SNode findByValue(int data) {        SNode sNode = head;        for (int i = levelCount - 1; i >= 0; --i) {            while (sNode.forwards[i] != null && sNode.forwards[i].data < data) {                sNode = sNode.forwards[i];            }        }        if (null != sNode.forwards[0] && sNode.forwards[0].data == data) {            return sNode.forwards[0];        }        return null;    }复制代码

测试结果

根据打印结果，它的结构大致是这样的

根据查找的打印结果可以看出，level最高级为8级，查到第5级就能查出结果，非常高效。

end

您的点赞和关注是对我最大的支持，谢谢！