跳表(SkipList)设计与实现(java)

前言

跳表是面试常问的一种数据结构，它在很多中间件和语言中得到应用，我们熟知的就有Redis跳表。并且在面试的很多场景可能会问到，偶尔还会让你手写试一试(跳表可能会让手写，红黑树是不可能的)，这不，给大伙复原一个场景

但你别慌，遇到蘑菇头这种面试官也别怕，因为你看到这篇文章了(得意

对于一个数据结构或算法，人群数量从听过名称、了解基本原理、清楚执行流程、能够手写 呈抖降的趋势。因为很多数据结构与算法其核心原理可能简单，但清楚其执行流程就需要动脑子去思考想明白，但是如果能够把它写出来，那就要自己一步步去设计和实现。可能要花很久才能真正写出来，并且还可能要查阅大量的资料。

而本文在前面进行介绍跳表，后面部分详细介绍跳表的设计和实现，搞懂跳表，这一篇真的就够了。

快速了解跳表

跳跃表(简称跳表)由美国计算机科学家***William Pugh发明于1989年***。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。

跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据远程桌面结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多。

在这里你可以看到一些关键词：链表(有序链表)、索引、二分查找。想必你的脑海中已经有了一个初略的印象，不过你可能还是不清楚这个"会跳的链表"有多diao，甚至还可能会产生一点疑虑：跟随机化有什么关系？你在下文中很快就能得到答案！

回顾链表，我们知道链表和顺序表(数组)通常都是相爱相杀，成对出现，各有优劣。而链表的优势就是更高效的插入、删除。痛点就是查询很慢很慢！每次查询都是一种O(n)复杂度的操作，链表估计自己都气的想哭了

这是一个带头结点的链表(头结点相当于一个固定的入口，不存储有意义的值)，每次查找都需要一个个枚举，相当的慢，我们能不能稍微优化一下，让它稍微跳一跳呢？答案是可以的，我们知道很多算法和数据结构以空间换时间，我们在上面加一层索引，让部分节点在上层能够直接定位到，这样链表的查询时间近乎减少一半，链表自己虽然没有开心起来，但收起了它想哭的脸。

这样，在查询某个节点的时候，首先会从上一层快速定位节点所在的一个范围，如果找到具体范围向下然后查找代价很小，当然在表的结构设计上会增加一个向下的索引(指针)用来查找确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很大的时候，它依旧很慢很慢。我们都知道二分查找是每次都能折半的去压缩查找范围，要是有序链表也能这么跳起来那就太完美了。没错跳表就能让链表拥有近乎的接近二分查找的效率的一种数据结构，其原理依然是给上面加若干层索引，优化查找速度。

通过上图你可以看到，通过这样的一个数据结构对有序链表进行查找都能近乎二分的性能。就是在上面维护那么多层的索引，首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。

对于理想的跳表，每向上一层索引节点数量都是下一层的1/2.那么如果n个节点增加的节点数量(1/2+1/4+…)<n。并且层数较低，对查找效果影响不大。但是对于这么一个结构，你可能会疑惑，这样完美的结构真的存在吗？大概率不存在的，因为作为一个链表，少不了增删该查的一些操作。而删除和插入可能会改变整个结构，所以上面的这些都是理想的结构，在插入的时候是否添加上层索引是个概率问题(1/2的概率)，在后面会具体讲解。