数据结构与算法——跳表

1. 概述

前面说到了二分查找，并且它是基于顺序表结构的，即数组，如果直接用于链表，时间复杂度会比较的高，是 O(logn)，一般我们不会这样做。那么有没有基于链表的二分查找呢？答案就是今天说到的跳跃链表。

2. 跳表长什么样子？

对于一般的链表，我们进行查找的话，需要遍历整个链表，就像下面这样：如果我们要找节点 9 ，需要遍历 9 个节点。

如果我们在原始链表之上建立一级链表，会是什么样子呢？如下图：

新建立的一级链表，我们叫做索引层或是索引，那么建立了一级索引之后，再来查找节点 9，会遍历多少节点呢？我们从第一级索引中开始查找，到了节点 9 的时候，通过向下的指针，可以找到节点 9，总共遍历了 6 个节点，相比没有索引，查找的效率提高了。

这样效果其实还不是非常的明显，如果我们再加上几级索引，查找会不会更快呢？

如上图，总共建立了三级索引，现在查找节点 9 ，只需要遍历 5 个节点了，查找的效率再一步提升了。其实，上面我举的例子，总共只有 10 个节点，所以看不出来性能有多大的提升，但是在实际的开发中，存储的数据成千上万，那么跳表的效率就更能体现了。

3. 跳表分析

通过上面的理解，你应该知道了跳表，其实就是通过建立多级索引来提升查找效率的一种数据结构。跳表的查询时间复杂度是 O(logn)，跟二分查找一样，空间复杂度是 O(n)，因为每一级建立的索引的节点个数都是上一级的一半，总共加起来就还需要原始链表的空间大小。
综合分析，其实你已经不能看到，跳表其实利用的是空间换时间的思想。

其实跳表不只是能够在 O(logn) 内查询数据，并且也可以高效的插入和删除数据，时间复杂度还是 O(logn)。

删除操作其实很简单，找到之后直接删除节点即可。
插入操作也类似，因为整个链表是有序的，所以查找之后，直接插入。只不过这里涉及到一个动态更新的问题。一般的动态数据结构都会维持平衡，保证插入查询操作的性能不会下降。
例如跳表，假如没有动态更新，则可能会出现插入之后，链表节点特别集中的问题：

在极端的情况下，跳表还是会退化为链表。
所以跳表借助了随机函数这种方式来维持整个索引的平衡性，每插入一个节点，都会生成一个随机函数 k，然后不仅是在原始链表中插入这个节点，还会在 1-k 层索引中插入这个节点。

4. 跳表实现

跳表的具体实现其实还是比较复杂的，代码理解起来比较的困难，这里我就不贴出来了，大家有兴趣的可以到我的 Github 上面参考借鉴。点击进入我的 Github

只不过我们也不用死扣跳表的代码实现，在实际的开发环境中，我们能够利用已有的实现就很不错了，这就是避免重复造轮子。例如在 Java 中已经有跳表的两个实现类，分别是 ConcurrentSkipListSet 和 ConcurrentSkipListMap，并且是线程安全的。