本文参考资源：

【数据结构与算法】之跳表（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在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。
• ……