1。跳表的概念跳表是一种动态数据结构，可以支持快速的插入、删除和查找操作。写起来不是很复杂，甚至可以代替红黑树。skiplist的空间复杂度为O(n)，时间复杂度为O(logn)。对于一个有序的单向链表，如果要查找一条数据，只能从头到尾遍历链表。为了提高查询效率，我们可以利用索引在链表上建立一级索引，比如提取每两个链表节点中较小的节点作为一级索引节点（对于keyvalue，只能保留keyvalue），一级索引节点也可以用同样的方法提取为二级索引节点，如图，就是跳表的结构。对于下图，如果要查询10的数据，那么先在二级索引层遍历。遍历到二级索引中的索引节点7后，发现下一个索引节点的值为13，那么数据节点10一定在这两个inode之间。然后通过下指针，下降到一级索引层，继续遍历查找。此时遍历到一级索引节点9，下一个索引节点的值为13，然后通过下指针继续下行到原链表继续遍历查找，从而找到10.dataof10.综上所述，skiptable是一个值有序的链表建立多级索引后的数据结构。通过上面的查找方式，我们可以看到一种类似于二叉查找树的查找方式，所以跳表查找类似于链表的“二分查找”算法。空间复杂度假设原链表的大小为n，则一级链表有n/2个节点，二级索引有n/4个节点，最顶层有2个节点。那么需要的索引节点总数因此，跳表的总空间复杂度仍然是O(n)，也就是说，使用跳表查询数据时，需要增加n个节点的存储空间。虽然空间复杂度保持不变，但额外使用的空间还是有点多了。那么，可以采用如下方法尽可能降低索引的空间复杂度：可以将多几个节点提取到一个节点中，比如每3个节点或者5个节点提取到一个节点中。虽然子空间复杂度仍然是O(n)，但所需索引节点的数量实际上要少得多。★在实际的软件开发中，原来的链表可能会存储很大的对象，而索引节点只需要存储键值和少数几个指针，不需要存储对象。这时候索引节点占用的额外空间就比较大了。与大物件相比，它其实很小，可以忽略不计。》2.跳表的操作2.1.单向链表查询的查找时间复杂度是O(n)，那么对于多级索引的跳表，查询某条数据的时间复杂度是多少呢？query有没有提升？效率呢？假设链表有n个节点，我们假设每两个节点抽取一个节点作为上层的索引节点，那么第一层的索引节点个数为n/2，第二层索引节点个数为n/2^2，以此类推，第k层索引节点个数为n/2^k。假设索引层最高层h,而最高层的索引节点有2个节点,那么我们得到,加上原链表的层一共有层.当我们在跳表中查询某条数据时,如果每一层需要编译m片，那么跳表中一条数据的时间复杂度为O(mlogn)。由于我们是每两个节点提取一个节点，所以只有ly最高层有两个节点，所以每一层最多可以比较3个节点。比如我们要找的数据是x，遍历到第k个索引层的y节点后，发现如果x大于y但小于y后面的z节点，那么y的down指针会从k级索引下降到k-1级索引，最多只需要遍历k-1级索引中的3个节点。因此，跳表查询数据的时间复杂度为O(logn)，与二分查找相同。但是，这种查询效率的提升需要提前建立多层次的索引，以及以空间换时间的设计思路。2.2.在单向链表中插入，如果定位到要插入的位置，插入节点的时间复杂度很低，为O(1)。但是定位要插入的位置的时间复杂度是O(n)，比如原链表中的数据是有序的，那么就需要遍历链表找到要插入的位置。对于跳表来说，由于查找节点的时间复杂度是O(logn)，而插入实际上是在链表中插入，所以插入操作的时间复杂度是O(logn)。2.3.Delete删除操作类似，但是如果这个结点也出现在索引中，除了删除原链表中的结点外，还要在索引中删除。由于删除节点需要先行节点，所以使用双向链表删除节点非常方便。综上所述，删除操作的时间复杂度也可以是O(logn)。2.4.索引更新时如果我们不停地向跳表中插入数据而不更新索引节点，那么两个索引节点之间可能会有很多数据。在极端情况下，跳表可能会退化为单向链表。因此，我们需要一些手段来保持索引和原始链表大小的平衡，也就是说，如果链表中的节点数量增加，索引节点的数量也会相应增加，以避免性能下降搜索、插入和删除。跳表通过随机函数来维持这种平衡。当我们将数据插入跳表时，我们使用随机函数来确定将其添加到哪些索引层。例如，如果随机函数产生一个值k，那么我们从第一层到第k层在k层索引中添加相应的索引节点。★对于平衡二叉树，如红黑树、AVL等，都是通过左右旋转来保持左右子树的平衡。》3、应用Redis中的有序集合是通过skiptable实现的，同时也使用了hashtable。为什么要用jumptable而不是红黑树呢？最重要的是jumptable支持区间查找。Redis中的核心操作有序集合支持的主要有：插入、删除、查找一条数据；按照区间查找数据（例如查找值在[100,356]之间的数据）迭代输出中的有序序列其中插入、删除、查找操作，红黑树也可以很快完成，时间复杂度也是O(logn)。但是根据区间查找数据的操作，红黑树的效率没有跳表那么高，跳表可以做到O(logn)时间复杂度定位区间起点，然后在原链表中依次向后遍历，其实在一个有序集合中，每个成员对象有两个我重要属性：键和值。有时我们不仅需要按值查找数据，还需要按键查找数据。我们可以把成员对象按照value组织成一个跳表结构，这样这时候根据value查找对象很方便，但是当我们想通过key查找对象的时候就会很麻烦。那么，我们就可以结合哈希表，相当于结合了哈希表和跳转表。这时根据key查找、删除、插入一个成员对象的时间复杂度就变成了O(1)4.总结跳表是一种动态数据结构，它利用空间换时间的设计思想来实现提高查询效率。简单来说，就是在原有链表的基础上，构建多级索引层，提高查询效率，在查找的方式上有点类似于二分查找。综上所述，跳表的查询、插入、删除的时间复杂度为O(logn)，而空间复杂度为O(n)。5、参考https://juejin.im/post/6844903446475177998本文转载自微信公众号“多选参数”，可通过以下二维码关注。转载本文请联系多选参数公众号。
