跳表及其应用

当我们谈到二分查找时提到其实现只能基于数组，因为数组具有随机访问的特点，那么如果数据在链表中，就不能用二分查找了吗？其实也不是，只要对链表稍加改造，也可以实现类似于二分查找的方式，我们把这种改造后的链表称为跳表

**

1. 什么是跳表

对于单链表，我们查找数据是需要从头遍历链表的，这样的话性能就没有那么高，如下图所示：

如果要查找18，只能一个一个的去遍历才能找到，那么，可不可以让速度快一点呢？当然可以，我们可以对原有链表加一级索引，通过索引查找，如下图所示：

这样一来，查找18只需要遍历7个节点，而不是像上面那样，遍历18个节点，是不是快了许多。

加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了，而且，我们不仅只能加一级索引，还可以继续加：


针对此图，查找62的话，相比遍历整个链表，那得快了多少哦，这速度不香吗！！！

总结：这种链表加多级索引的结构，就是跳表
**

2. 性能分析

3. 动态更新索引

当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表

所以，当插入元素过多时，我们需要动态增加所以，避免复杂度退化，以及查找、插入、删除操作性能下降，我们把这种动态增加索引的方式叫做随机函数，比如随机函数生成了K，那么我们就把元素添加到K级索引

4. 在Redis中的应用

为什么 Redis 要用跳表来实现有序集合，而不是红黑树

Redis 中的有序集合支持的核心操作:

• 插入一个数据；

• 删除一个数据；

• 查找一个数据；

• 按照区间查找数据（比如查找值在[100, 356]之间的数据）；

• 迭代输出有序序列

插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

Redis 之所以用跳表来实现有序集合，还有其他原因，比如，跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗

不过，跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些，很多编程语言中的 Map 类型都是通过红黑树来实现的。我们做业务开发的时候，直接拿来用就可以了，不用费劲自己去实现一个红黑树，但是跳表并没有一个现成的实现，所以在开发中，如果你想使用跳表，必须要自己实现。