摘要：跳表分析通过上面的理解，你应该知道了跳表，其实就是通过建立多级索引来提升查找效率的一种数据结构。一般的动态数据结构都会维持平衡，保证插入查询操作的性能不会下降。例如在中已经有跳表的两个实现类，分别是和，并且是线程安全的。
1. 概述
前面说到了二分查找，并且它是基于顺序表结构的，即数组，如果直接用于链表，时间复杂度会比较的高，是 O(logn)，一般我们不会这样做。那么有没有基于链表的二分查找呢？答案就是今天说到的跳跃链表。
2. 跳表长什么样子？
对于一般的链表，我们进行查找的话，需要遍历整个链表，就像下面这样：如果我们要找节点 9 ，需要遍历 9 个节点。
如果我们在原始链表之上建立一级链表，会是什么样子呢？如下图：
新建立的一级链表，我们叫做索引层或是索引，那么建立了一级索引之后，再来查找节点 9，会遍历多少节点呢？我们从第一级索引中开始查找，到了节点 9 的时候，通过向下的指针，可以找到节点 9，总共遍历了 6 个节点，相比没有索引，查找的效率提高了。
这样效果其实还不是非常的明显，如果我们再加上几级索引，查找会不会更快呢？
如上图，总共建立了三级索引，现在查找节点 9 ，只需要遍历 5 个节点了，查找的效率再一步提升了。其实，上面我举的例子，总共只有 10 个节点，所以看不出来性能有多大的提升，但是在实际的开发中，存储的数据成千上万，那么跳表的效率就更能体现了。
3. 跳表分析
通过上面的理解，你应该知道了跳表，其实就是通过建立多级索引来提升查找效率的一种数据结构。跳表的查询时间复杂度是 O(logn)，跟二分查找一样，空间复杂度是 O(n)，因为每一级建立的索引的节点个数都是上一级的一半，总共加起来就还需要原始链表的空间大小。
综合分析，其实你已经不能看到，跳表其实利用的是空间换时间的思想。
其实跳表不只是能够在 O(logn) 内查询数据，并且也可以高效的插入和删除数据，时间复杂度还是 O(logn)。
删除操作其实很简单，找到之后直接删除节点即可。
插入操作也类似，因为整个链表是有序的，所以查找之后，直接插入。只不过这里涉及到一个动态更新的问题。一般的动态数据结构都会维持平衡，保证插入查询操作的性能不会下降。
例如跳表，假如没有动态更新，则可能会出现插入之后，链表节点特别集中的问题：
在极端的情况下，跳表还是会退化为链表。
所以跳表借助了随机函数这种方式来维持整个索引的平衡性，每插入一个节点，都会生成一个随机函数 k，然后不仅是在原始链表中插入这个节点，还会在 1-k 层索引中插入这个节点。
4. 跳表实现
跳表的具体实现其实还是比较复杂的，代码理解起来比较的困难，这里我就不贴出来了，大家有兴趣的可以到我的 Github 上面参考借鉴。点击进入我的 Github
只不过我们也不用死扣跳表的代码实现，在实际的开发环境中，我们能够利用已有的实现就很不错了，这就是避免重复造轮子。例如在 Java 中已经有跳表的两个实现类，分别是 ConcurrentSkipListSet 和 ConcurrentSkipListMap，并且是线程安全的。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/73914.html
摘要：同时，也提供了一个基于的实现类，底层基于红黑树设计，是一种有序的。可以看成是并发版本的，但是和不同是，并不是基于红黑树实现的，其底层是一种类似跳表的结构。上述所有构造器都调用了方法方法将一些字段置初始化，然后将指针指向新创建的结点。 showImg(https://segmentfault.com/img/remote/1460000016201159); 本文首发于一世流云专栏：ht...
摘要：跳表全称叫做跳跃表，简称跳表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。 前言 增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表...
阅读 866·2023-04-25 19:17
阅读 2150·2021-09-10 11:26
阅读 1869·2019-08-30 15:54
阅读 3399·2019-08-30 15:53
阅读 2662·2019-08-30 11:20
阅读 3367·2019-08-29 15:12
阅读 1207·2019-08-29 13:16
阅读 2366·2019-08-26 12:19
