跳表的数据结构已经成为Redis面试的高频考点。在这两年还没有这个卷的时候，从开始学习到拿到大厂offer的过程，你可能都没听说过跳表这个数据结构。那么什么是跳表呢？它是干什么用的？AVL树就是红黑树，你懂的，没错，跳表跟他做的类似。我举个例子让大家明白。假设当前有一个有序序列：[2,11,22,33,44,52,63]我们想基于单向链表的思想设计一个数据结构，实现一个查找时间复杂度O（登录）。在单向链表的情况下，它的结构如下所示。跳转到表1，当然是这个结构，找一个合适的时间复杂度O(n)，那怎么改呢？然后换题：我们平时做算法题和手撕代码面试的时候，写一个时间复杂度O(n)的解的时候，面试官摇头问你有没有更好的办法，你会怎么做？常见复杂度O(nlogn)O(n)O(logn)O(1)，要优化，一步走几步，只能到O(logn)。复杂度为logn的最常见算法是什么？当然是二分法！思路是对的，那么如何将二分法思维融入到链表中呢？还是单链表指针？一边动刀一边动刀？让指针不仅指向后面的元素，还要跨越几个节点，指向更远的后面元素？类似于二叉搜索树？首先我们看一下这个数组对应的二叉查找树长什么样子。跳表2当然，由于我们的结构是单向链表，所以只能有小值指向大值。这个二叉树必须改变。跳转表2在里面好像有点意思，然后加上原来单向链表的属性。跳表2的接线有点乱。按照单链表的布局显示方式改一下：（值得注意的是我们需要新建一个数组项，每个数组项存储一个指针，指向二叉查找树每一层的最左边一层刚才边节点）（感觉越来越像B+树了（雾））再看查找逻辑：当保存的节点数小于要查找的小时数时，跳表会继续访问这一层上面的下一个节点。当不满足时，跳表会使用当前查找节点的指针数组的下一层指针，然后沿着下一层指针继续查找。对于这个数据结构，我们需要从上到下查询三个链表，比如我们要查询大于35的数，先找到左边数组中的第一个，发现中间节点是33，也就是相比之下，小于35。发现33小于35，跳转到下一个节点。如果发现该节点为Null，则跳转到33的下一层节点。发现52大于35，则跳转到下一层节点。发现44大于35，跳下一层节点，但由于这是最后一层节点，即44是大于33的第一个数，满足最终条件，则找到第一个大于35的数字。我们知道，如果插入操作是针对二叉平衡树设计的，会特别麻烦。二叉平衡树思想修改的跳表也是如此。对于我们的情况，每次添加或减去一个新节点时，都需要更改每个节点的高度。.有没有专家改进？既然二叉平衡树改成了这四种不同的图像，那为什么不再改一下，是不是可以让它不平衡的同时保证搜索效率呢？说实话，还真有可能，我们看看这只跳表。跳表1虽然这个跳表和我们刚才讲的跳表相比有点奇形怪状，但是按照刚才的搜索思路还是可以做更好的查询工作的。而且由于表格如此奇形怪状，因此添加或删除新元素并保持其他节点的高度不变并不是什么大问题。而且神奇的是，如果我们随机生成新插入节点的高度（每次随机大于p，然后增加高度，小于p时停止），那么其他节点的高度保持不变，搜索效率还是O(logn)，不会像二叉查找树那样直接退化到O(logn)。有兴趣看推导的同学点个赞，如果点赞数超过100，就写个推导吧。（目前面试还没到证明跳表时间复杂度的地步，不知道怎么推。）
