总结

跳跃表是一种有序的数据结构，他通过在每个节点中维持多个指向其他节点的指针，从而到达快速访问节点的目的（其实就是多层链表）
image.png

链表

前面说了，跳跃表其实就是多层链表，所以先复习一下链表

链表的特点是增删快，查找慢，查找的时间复杂度可以到达 O(n)
image.png
如果我们要从 1 找到 5，需要走五步，那怎么快一点呢，就是把步子迈大点

跳跃表

所以可以将单链表变成这样

image.png
其实就是在原有链表上简历索引，每间隔 N 个节点提取到上一级，我们把抽出来的那一级叫做索引

跳跃表的查询

  • 同样，我们要到节点 5，我们先在索引层中遍历，比较两次即可到达目的地，下降到链表层获取目标节点即可
  • 如果要找到 6，同样先在索引层中遍历，当遍历到索引层值为 5，下一个值为 7 时，我们的目标节点肯定在这两个节点之间，这时候我们下降到链表层继续遍历即可

如果我们想进一步提高查询效率，可以继续提取
image.png
查询方式相同

可以发现，当数据量庞大的时候，多级索引的建立可以大大提高查询速度，典型的空间换时间方式

我们熟悉的 redis，底层采用的就是跳跃表

往跳跃表增加数据

首先先在索引层比较，迅速锁定到目标大概位置
image.png
然后回到链表层比较，得到目标位置
image.png

最后将数据插入
image.png

索引层节点的提拔

当有许多数据新增到跳跃表中的时候，原有的索引节点不够用，因此需要进行补充
索引层的节点其实来自于下一层的节点，那被提升到上一层的操作被称为提拔，设计者采用“抛硬币”的方式进行提拔，也就是每个节点被提拔的概率是百分之五十。
（假设紫色为刚新增的节点）
image.png

采用这种提拔的方式是因为跳跃表的删除和添加是不可预测的，很难有一种有效的算法来保证跳跃表的索引部分始终均匀，采用这种方式虽然不能保证索引绝对均匀分布，但是可以大体均匀

所以跳跃表的增加可以总结为以下几步

  • 新节点和各层索引节点逐一比较，确定原链表的插入位置，时间复杂度为 O(logN)
  • 把新节点插入到原链表中，时间复杂度为 O(1)
  • 使用抛硬币的方式，决定新节点是否提升为上一级索引，百分之五十概率，时间复杂度为 O(logN)

总体上跳跃表的时间复杂度为 O(logN)，空间复杂度为 2N => O(N)

往跳跃表删除数据

在索引层找到要删除的节点，然后从上到下依次删除即可，如果某一层索引在删除后只剩下一个及诶单，那么整一个层就可以删掉了，因此只有一个的节点并没有什么用
image.png
跳跃表的删除细节步骤如下

  • 自上而下，查找第一次出现的节点的索引，并逐层找到每一层对应的节点，时间复杂度为 O(logN)
  • 删除每一层查找到的节点，如果该层只剩下一个节点，删除整一个层（原始链表除外）O(logN)

总体上，跳跃表的删除操作的时间复杂度为 O(logN)

跳跃表与二叉查找树

跳跃表的优点是维持结构的成本比较低，完全依靠随机，而二叉查找树在多次插入删除后需要 Rebalance 来重新调整结构平衡

参考：
https://www.jianshu.com/p/3a6003010fc2
https://www.jianshu.com/p/dc252b5efca6