引出

上一篇讲到二分查找，数据结构使用的是数组。为什么不能使用链表呢。
原因是因为数组可以随机访问，也就是通过数据下标，直接可以定位到数组的中点。
而链表如果要定位到链表的中点，必须遍历n/2链表。
那，链表如果做到二分查找呢，有一个空间换时间的做法，那就是跳表

跳表

原理

原始链表

原始链表.png

对原始链表加一层”索引“，每两个节点提取一个节点到上一层，然后用down指针连接到下一层

第一级索引.png

现在我们查询16，先从第一次索引检索到13，发现下一个节点是17，比16大，就向下到原始链表再遍历。但很显然，现在一级索引还是太”长“了，那么就再加一层

第二级索引.png

现在我们想查询16呢
1 -> 7 -> 13 -> 16， 以牺牲空间把二分查找的索引建出来，是不是很完美。

时间复杂度

都说的了是以牺牲空间的方式做到了二分查找，所以时间复杂度和二分查找一样：O(logn)

空间复杂度

因为建立了索引，每两个节点建一个，所以空间复杂度是每层节点的和
n/2 + n/4 + n/8 + .... + 4 + 2 = n-2
所以空间复杂度为：O(n)

索引动态变更

涉及到索引，就涉及到索引的变更，那就引出了，原始链表新增元素、删除元素，索引的变化。
新增、删除的时间复杂度就不展开了，分两步

1. 找到插入或者删除的位置，跳表的二分查找，时间复杂度O(logn)
2. 新增和删除元素，链表的新增和删除只涉及指针的改变，时间复杂度O(1)

言归正传
如果第一次构建完跳表，后面索引不变动，那插入的数据都在一个区间里，那这个区间就退化成链表了。

跳表退化.png

插入

那就在插入的时候，同时也加上索引就好啦。

这里涉及一个方法，在插入之前，先判断，该元素需要在哪一级索引上建索引。
该方法返回

• 1：不建索引 概率1/2
• 2：在一级索引上建索引 概率 1/4
• 3：在二级索引上建索引 概率 1/8（ps:在上级建索引，下级都会建）
• .......以此类推

不建索引.png 建一级索引.png 建二级索引.png

randomLevel() 方法

• randomLevel() 方法，随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且有 1/2的概率返回 1、1/4的概率返回 2、1/8的概率返回 3 ...
• randomLevel() 方法返回 1 不建索引、返回2建一级索引、返回 3 建二级索引、返回 4 建三级索引 ...

直接上代码，没有入参，说随机肯定就是随机

/**
     * 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
     *  1/2 的概率返回 1
     *  1/4 的概率返回 2
     *  1/8 的概率返回 3 以此类推
     *
     *  SKIPLIST_P 设置为0.5
     */
    private int randomLevel() {
        int level = 1;
        // 当 level < MAX_LEVEL，且随机数小于设定的晋升概率时，level + 1
        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) {
            level += 1;
        }
        return level;
    }

删除

删除元素，如果该元素上有索引，那把索引一起删了

删除元素.png