浅入浅出“跳表”

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：

github.com/chaoaiqi/st…

定义

跳表是快速查询一个有序连续元素的数据链表。它虽然是链表，但是它集数组和链表与之所长，跳表的平均查找和插入时间复杂度都是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方法，为了便于测试，查看日志

该用法随机了level次，主要是用来防止伪随机的，当随机出奇数的时候，level+1

插入

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

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

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

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

over

删除

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

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

查找

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

forwards[0].data == data 即可

测试结果

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

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

end

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