当我们谈到二分查找时提到其实现只能基于数组,因为数组具有随机访问的特点,那么如果数据在链表中,就不能用二分查找了吗?其实也不是,只要对链表稍加改造,也可以实现类似于二分查找的方式,我们把这种改造后的链表称为跳表
1. 什么是跳表
对于单链表,我们查找数据是需要从头遍历链表的,这样的话性能就没有那么高,如下图所示:
如果要查找18,只能一个一个的去遍历才能找到,那么,可不可以让速度快一点呢?当然可以,我们可以对原有链表加一级索引,通过索引查找,如下图所示:
这样一来,查找18只需要遍历7个节点,而不是像上面那样,遍历18个节点,是不是快了许多。
加来一层索引之后,查找一个结点需要遍历的结点个数减少了,也就是说查找效率提高了,而且,我们不仅只能加一级索引,还可以继续加:
针对此图,查找62的话,相比遍历整个链表,那得快了多少哦,这速度不香吗!!!
总结:这种链表加多级索引的结构,就是跳表
**
2. 性能分析
3. 动态更新索引
当我们不停地往跳表中插入数据时,如果我们不更新索引,就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表
所以,当插入元素过多时,我们需要动态增加所以,避免复杂度退化,以及查找、插入、删除操作性能下降,我们把这种动态增加索引的方式叫做随机函数,比如随机函数生成了K,那么我们就把元素添加到K级索引
4. 在Redis中的应用
为什么 Redis 要用跳表来实现有序集合,而不是红黑树
Redis 中的有序集合支持的核心操作:
- 插入一个数据;
- 删除一个数据;
- 查找一个数据;
- 按照区间查找数据(比如查找值在[100, 356]之间的数据);
- 迭代输出有序序列
插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。
Redis 之所以用跳表来实现有序集合,还有其他原因,比如,跳表更容易代码实现。虽然跳表的实现也不简单,但比起红黑树来说还是好懂、好写多了,而简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗
不过,跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些,很多编程语言中的 Map 类型都是通过红黑树来实现的。我们做业务开发的时候,直接拿来用就可以了,不用费劲自己去实现一个红黑树,但是跳表并没有一个现成的实现,所以在开发中,如果你想使用跳表,必须要自己实现。