跳表是通过对链表建立多级索引实现的一种可以在插入、删除、查找、取连续区间数据性能极其卓越的动态数据结构。时间复杂度都是 O(logn)。
理解跳表
如果对一个长度为 n 的链表，每两个元素取第一个元素建立索引，那么查找元素的时间就可以降低 1/2，再对这层索引，仍每两个元素取第一个元素建立索引，在这一层查找元素的时间就会降低为下一层索引的 1/2，即这一层总的查找时间为原来的 1/2 * 1/2 = 1/4……最终顶层为两个索引元素，整个数据结构的查找时间就降低为 O(logn)，这就是跳表。
跳表到底有多快
假设从底到顶每层索引标记为第 1 层索引，第 2 层索引……每层节点的数量是 n / (2^k)。若顶层有两个节点，那么总共有 log[2]n-1 层索引，包含底层链表，就是 log[2]n 层，又每层需要遍历不超过 3 个节点，总共的查找时间就是 O(3 * logn) = O(logn)。
从这个角度看，我们通过空间换时间，用链表实现了 “二分查找”。
跳表是不是很消耗内存
如果我们在链表中存储的是大对象，我们在索引中只是保存要比较的 key。那这点空间又其实可以忽略。
在动态插入和删除时维持这个数据结构
跳表如果插入元素时索引没有即使地动态建立，那就可能造成索引和原始链表地大小不平衡，导致复杂度退化到链表级别。
当我们往跳表中插入数据的时候，我们可以根据随机函数选择将这个数据插入到部分索引层中。比如随机函数生成了值 K，那我们就将这个结点添加到第 1 级到第 k 级的索引之中。
随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。
在跳表中删除元素时，除了要删除链表中的，还要删除索引中的，这就要拿到并保持前驱节点，或者用双向链表。
跳表在 redis 中的实现
redis 中的有序集合是通过跳表和散列表来实现的。有序集合的功能大概有以下几点：
- 插入一个元素
- 查找一个元素-
- 删除一个元素
- 按照区间查找数据
- 迭代输出有序序列
其中，插入、删除、查找、迭代输出有序序列这几个操作，红黑树也可以完成，复杂度一样。但是按照区间查找数据这个功能，红黑树实现的效率就没有跳表高了。
跳表只需要在 O(logn) 时间内定位到区间的开头，然后往后遍历就可以了。
跳表是否可以取代红黑树
很多编程语言都有现成的红黑树实现的 Map，我们可以拿来直接使用，而跳表需要我们手动实现，在业务开发时我们要除了考虑算法的性能，还要考虑实现的代价、维护的代价。比较下来，还是直接使用现成的工具最好，除非有特定的需求，我们再构建相应的数据结构实现需求。
网友评论