阅读 749

以后谁再问你【跳跃表】,就把这文章扔给他!

先让我们看一个问题:如果要存一组有序的 int 型数据集合,我们可以如何实现?

  1. 数组

可能大多数同学最先想到的是用数据实现,将有序的数据集合存放在数据中,可以使用二分法进行查找,效率比较高,但是对于新增和删除的操作并不友好,因为这些操作都需要移动后面位置的元素。

  1. 链表

那么有没有什么数据结构可以让查询、新增、删除操作都变得很快呢?这就是我们今天要介绍的跳跃表了,让我们看几张图,很容易理解。

跳跃表

跳跃表-底层数据链路
跳跃表-底层数据链路

如上图,一个有序的链表,如果要找值为 50 的节点,需要从第一个节点开始遍历,查询最后才能找到值为 50 的节点。

我们给这个链表加一层索引,如图:

跳跃表-一级索引
跳跃表-一级索引

我们按照一级索引来查询(橙色查询路线),可以发现我们至少可以少遍历一半的节点。

还觉得有些慢?,那么再增加一层,再加一层,如图:

跳跃表-二级索引
跳跃表-二级索引
跳跃表-三级索引
跳跃表-三级索引

是不是更快地找到我们需要的节点了,当然这里的节点数量不够多,如果节点数量非常多,查找效率提升会更加明显。

如果需要找中间的某个节点,比如寻找 42 ,过程大概是这样的:

跳跃表-三级索引-寻找42
跳跃表-三级索引-寻找42

插入节点

看懂了跳跃表的数据结构,那么就很容易理解节点的插入操作了,基本上两步操作就可以实现:在最底层的数据链表中插入数据,然后调整索引;

其中每一层的索引链表中是否需要增加新增的节点,其实并没有什么标准答案,我们尽量做到索引的平均分布即可,常用的就是【随机判断】决定是否需要新增或调整索引,当有新节点插入的时候,通过概率算法判断这个节点需要插入到几级节点中。

比如:

  • 底层数据链表有 N 个元素,随机选择 N/2 个元素作为 1 级索引,随机选择 N/4 个元素作为 2 级索引…一直到顶层索引;
  • 新插入数据节点,1/2 概率不插入任何一级索引,1/4 概率返回需要插入 1 级索引,1/8 概率返回需要插入到 2 级索引,以此类推;
  • 这里要注意一点,插入 2 级索引的时候,同时也需要插入 1 级索引;也就是插入 n 级索引的时候,同时也要插入 1~( n-1 ) 级索引。
跳跃表-三级索引-插入节点
跳跃表-三级索引-插入节点

删除节点

跳跃表删除节点就更简单了,删除数据节点,并删除每一层的索引节点(如果有的话)。

总结来说:

  1. 可以把跳跃表看成多个有序链表(最底层的数据链表+多层索引链表);

  2. 查找的过程中,从最长层开始查找,找到对应的区间再到下一层查找 ;

  3. 每个节点都有两个指针,分别指向右边和下边;

  4. 插入新节点时,随机判断该节点是否要插入索引,最高插入几级索引;

  5. 插入 n 级索引的时候,同时也要插入 1~(n-1) 级索引;

  6. 跳跃表和红黑树等平衡树相比,更容易实现,并且不需要维护平衡性;

  7. Redis 中的 ZSet 的一种实现方式是 skipList 与 hashTable 的结合;

  8. Google 的 LevelDB 、Facebook 的 RocksDB ,它们都是使用了跳跃表这种数据结构。

会点代码的大叔 | 文【原创】


敬请关注会点代码的大叔
敬请关注会点代码的大叔
关注下面的标签,发现更多相似文章
评论