只需要对链表稍加改造,就可以支持类似“二分”的查找算法。
我们把改造之后的数据结构叫做 跳表 Skip List
跳表的原理
跳表是在前一层链表基础上间隔1个元素抽出一层新的链表,并将新链表作为索引。
不断抽出新的索引链表,直到索引链表只剩2个元素。
(当然,跳表也可以间隔x个元素抽取索引链表,x>=2)
跳表索引动态更新
当我们不停地往跳表中插入数据时,如果我们不更新索引,就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表。
当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢?
我们通过一个随机函数,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
跳表的应用
跳表是一种各方面性能都比较优秀的动态数据结构,可以支持快速地插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。
Redis 中的有序集合(Sorted Set)就是用跳表来实现的。
Redis 之所以用跳表来实现有序集合,还有其他原因,比如跳表更容易代码实现。
虽然跳表的实现也不简单,但比起红黑树来说还是好懂、好写多了,而简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。
跳表的实现
留个坑(如果能想起来再填)