跳过列表

跳转到导航跳转在计算机科学中搜索，跳过列表是一种概率数据结构，其允许O(LOG⁡n){\DisplayStyle{\数学{O}}(\Logn)}搜索复杂度以及O(LOG⁡n){\DisplayStyle{{\数学{O}}(\logn)}插入复杂度在n{\DisplayStyle n}元素的有序序列内。因此，它可以获得排序数组的最佳特性(用于搜索)，同时维护允许插入的类似链表的结构，这在数组中是不可能的。快速搜索是通过维持子序列的链接层次结构实现的，每个连续的子序列跳过的元素比前一个更少(请参见右下图)。搜索从最稀疏的子序列开始，直到找到两个连续的元素，一个小于搜索的元素，一个大于或等于搜索的元素。通过链接的层次结构，这两个元素链接到下一个最稀疏的子序列的元素，在那里继续搜索，直到最后我们在全序列中搜索。跳过的元素可以是概率选择[2]，也可以是确定性选择[3]，前者更为常见。

跳过列表是按层构建的。底层是一个普通的有序链表。每一较高层都充当一条快速车道；对于下面的列表，其中层i{\displaystyle i}中的元素以某个固定概率p{\displaystyle p}出现在层i+1{\displaystyle i+1}中(p{\displaystyle p}的两个常用值是1/2{\displaystyle 1/2}或1/4{\displaystyle 1/4})。平均而言，每个元素出现在1/(1−p){\DisplayStyle 1/(1-p)}列表中，并且出现在所有列表中的最高元素(通常是跳过列表前面的特殊HEAD元素)。跳过列表包含⁡n{\DisplayStyle\LOG_{1/p}n\，}(即n{\DisplayStyle n}的对数底1/p{\DisplayStyle 1/p})列表。

对目标元素的搜索从顶部列表中的head元素开始，然后水平进行，直到当前元素大于或等于目标。如果当前元素等于目标，则已找到该元素。如果当前元素大于目标，或者搜索到达链表的末尾，则在返回到上一个元素并垂直下降到下一个较低的列表后，重复该过程。每个链表中的预期步数最多为1/p{\displaystyle 1/p}，这可以通过从目标向后跟踪搜索路径，直到到达出现在下一个更高列表中的元素或到达当前列表的开头来查看。因此，当p{\⁡{1}{p}为常量时，搜索的总预期成本为1p log1/pdisplaystyle{\tfrac{1}{p}}\log_{1/p}n}，其为O(log⁡n){\displaystyle{\数学{O}}(\logn)\，}。通过选择不同的p{\displaystyle p}值，可以在搜索成本与存储成本之间进行权衡。

用于跳过列表的元素可以包含多个指针，因为它们可以参与多个列表。

插入和删除操作的实现方式与相应的链表操作非常相似，不同之处在于必须将元素插入到多个链表中或从多个链表中删除元素。

O(N){\displaystyle{\mathcal{O}}(N)}操作强制我们以升序访问每个节点(例如打印整个列表)，提供了以最佳方式执行跳过列表的级别结构的幕后去随机化的机会，从而使跳过列表的搜索时间为O(⁡n){\displaystyle{\mathcal{O}}(\logn)}。(选择第i'；个有限节点的级别为1加上在i变为奇数之前可以重复除以2的次数。此外，负无穷大头的i=0，因为我们通常有为负和/或正无限节点选择可能的最高级别的特殊情况。)。但是，这也允许某人知道所有高于级别1的节点的位置并将其删除。

如果i为奇数并且i不是级别j上的最后一个节点，则随机选择是否将其提升至级别j+1。否则，如果i为偶数且节点i-1未提升，则将其提升至级别j+1结束(←)。如果重复j←j+1，则将其提升至级别j+1。

与去随机版本一样，只有在有其他原因需要运行O(N){\displaystyle{\mathcal{O}}时，才会执行准随机化

这种准随机性的优点是，它不会像去随机化的用户那样向敌方用户提供几乎同样多的与层次结构相关的信息。这是可取的，因为能够辨别哪些节点不在最低级别的敌意用户可以通过简单地删除较高级别的节点来悲观性能。(然而，Bethea和Reiter认为，尽管如此，对手仍然可以使用概率和定时方法来强制降低性能。[4])搜索性能仍然保证是对数的。

进行以下优化是很有诱惑力的：在下面写着“接下来，对于每一对……”的部分，忘掉为每对偶数对抛硬币的事。只需抛硬币一次，就可以决定是只促销偶数的还是只促销奇数的。代替O(nlog⁡n){\DisplayStyle{\Mathcal{O}}(n\logn)}掷硬币，将只有O(LogLogStyle N){\DisplayStyle{\Mathcal{O}}(\logn)}个硬币被抛出，而不是O(nlog⁡n){\DisplayStyle{\Mathcal{O}}(\logn)}个硬币。不幸的是，这使得恶意用户在猜测所有偶数编号的节点(在级别1或更高的节点中)都高于级别1之后，有50/50的机会是正确的。这是尽管他猜测特定节点对于某个整数N处于级别N的概率非常低的特性。

跳过列表不能提供与更传统的平衡树数据结构相同的绝对最坏情况性能保证，因为用于构建跳过列表的掷硬币操作总是有可能(尽管概率非常低[5])产生一个很差的平衡结构。然而，它们在实践中工作得很好，并且已经证明随机平衡方案比平衡二叉搜索树中使用的确定性平衡方案更容易实现。跳过列表在并行计算中也很有用，在并行计算中，可以在跳过列表的不同部分并行进行插入，而无需对数据结构进行任何全局重新平衡。这种并行性对于ad-hoc无线网络中的资源发现特别有利，因为可以使随机化跳过列表对任何单个节点的丢失具有鲁棒性。[6]。

如上所述，跳过列表能够快速O(LOG⁡n){\DisplayStyle{\Mathcal{O}}(\logn)}从排序的序列中插入和移除值，但是它仅具有在序列中给定位置的值的缓慢O(N){\DisplayStyle{\Mathcal{O}}(N)}查找(即返回第500个值)；但是，只要稍加修改，随机访问索引查找的速度就可以提高到O(Logdisplaystyle){\⁡{O}}(\logn)}。

对于每个链接，还要存储链接的宽度。宽度被定义为每个较高层快速车道链接正在穿越的底层链接的数量。

例如，以下是页面顶部示例中的链接宽度：

1 10 o->；o--->；o顶层1 3 2 5 o->；o-&>；o->；o->；O->；o级别3 1 2 1 2 32 o-->；o->；O Level 2 1 1 1 11 1 o-&o底层标题1 2 3 4 5 6 7 8 9 10 Nil节点节点。

请注意，较高级别链接的宽度是其下方组件链接的总和(即宽度10链接跨越宽度为3、2和5的链接)。因此，每个级别上所有宽度的总和是相同的(10+1=1+3+2+5=1+2+1+2+3+2)。

要为跳过列表编制索引并找到第i个值，请在遍历跳过列表的同时向下计数每个遍历的链接的宽度。只要即将到来的宽度太大，就会下降一个级别。

例如，要查找第五个位置(节点5)中的节点，请遍历顶层宽度为1的链接。现在还需要四个步骤，但是这一层的下一个宽度是十个，这太大了，所以下降一个层。遍历一个宽度为3的链接。由于宽度为2的另一个台阶太远，请下降到最底层。现在遍历宽度为1的最后一个链接，以达到目标运行总数5(1+3+1)。

函数lookupByPositionIndex(I)Node←Head I←i+1#≥i+1#don'；不将Head算作Level从上到下执行的步骤，而I Level节点。width[Level]do#如果下一步不太远I←i-node.width[Level]#减去当前宽度节点←节点。NEXT[Level]#在当前级别向前遍历重复返回节点。Value结束函数。

这种实现索引的方法在William Pugh的跳过列表食谱中的3.4节线性列表操作中有详细介绍。

跳过列表是一种概率数据结构，似乎有可能取代平衡树作为许多应用程序选择的实现方法。跳表算法具有与平衡树相同的渐近预期时间界，并且更简单、更快、占用更少的空间。

REDIS是用于POSIX系统的ANSI-C开放源码永久键/值存储，它在有序集的实现中使用跳过列表。[8]。

NessDB是一个非常快的键值嵌入式数据库存储引擎(使用日志结构合并(LSM)树)，它对其内存表使用跳过列表。

速度表是Tcl的快速键值数据存储，它使用跳跃列表作为索引和无锁共享内存。

Level db，一个由Google编写的快速键值存储库，提供从字符串键到字符串值的有序映射。

SkiMap使用跳过列表作为基础数据结构，为机器人地图系统构建更复杂的三维稀疏网格。[10]。

IOWOW是一个持久化的C11键/值存储库，它使用跳过列表作为其主要数据结构。

跳过列表用于运行介质(也称为移动介质)的有效统计计算。跳过列表还用于分布式应用程序(其中节点代表物理计算机，指针代表网络连接)，并用于实现高度可伸缩的并发优先级队列，锁争用较少，[11]甚至没有锁，[12][13][14]以及无锁并发字典。[15]还有几项美国专利用于使用跳过列表来实现(无锁)优先级队列和并发字典。[16]。

^a b Papadakis，Thomas(1993)。跳过列表和算法概率分析(PDF)(博士)。滑铁卢大学。

门罗，J·伊恩；帕帕达基斯，托马斯；塞奇威克，罗伯特(1992)。确定性跳过列表(PDF)。第三届ACM-SIAM离散算法年度研讨会论文集(SODA&39；92)。奥兰多，佛罗里达，美国：工业与应用数学学会，宾夕法尼亚州费城，美国。第367-375页。10.1145/139404.139478。

题名/责任者：Reiter，Michael K.。(2009年9月21日至23日)。具有不可预测时序的数据结构(PDF)。ESORICS 2009，第14届欧洲计算机安全研究研讨会。圣马洛，法国。第456-471页，§4和#34；跳过列表"；。电话：04444-1_28，电话：10.1007/978-3-642。ISBN978-3-642-04443-4。

^Sen，SanDeep(1991)。关于跳跃列表的一些观察"；。信息处理信函。39(4)：173-176。电话：90175-H，电话：10.1016/00200190(91)。

^Shah，Gauri(2003)。对等系统的分布式数据结构(PDF)(博士论文)。耶鲁大学。

威廉·普夫(1989年4月)。同时维护跳过列表(PS、PDF)(技术报告)。部门。美国马里兰州计算机科学学院。CS-TR-2222。

^Gregorio，Daniele de；Stefano，Luigi Di(2017)。SkiMap：一种高效的机器人导航地图框架。Arxiv：1704.05832[cs.CV]。

沙维特，N.；洛坦，I.(2000)。"；基于Skiplist的并发优先级队列"；(PDF)。第十四届国际并行与分布式处理学术研讨会论文集。IPDPS 2000。第263页。CiteSeerX：10.1.1.116.3489.。DOI：10.1109/IPDPS.2000.84594.。ISBN电话：978-0-7695-0574-9。

宋代尔，H.；Tsigas，P.(2003)。用于多线程系统的快速且无锁的并发优先级队列。国际并行与分布式处理学术研讨会论文集。第11页。CiteSeerX：10.1.1.113.4552.。DOI：10.1109/IPDPS.2003.1213189.。ISBN电话：978-0-7695-1926-5。

米哈伊尔·福米切夫(Fomitchev)；埃里克·鲁珀特(Ruppert)(2004年)。无锁链接列表和跳过列表(PDF)。程序。ACM年度交流会。论分布式计算原理(PODC)。第50-59页。10.1145/1011767.1011776。ISBN为1581138024。

Bajpai，R.；Dhara，K.；Krishnaswamy，V.(2008)。"；QPID：具有项目位置的分布式优先级队列"；。2008年IEEE并行和分布式处理及其应用国际研讨会。第215页。DOI：10.1109/ISPA.2008.90.。ISBN电话：978-0-7695-3471-8。

宋代尔，香港；Tsigas，P.(2004)。可伸缩且无锁的并发字典(PDF)。2004年ACM应用计算研讨会论文集-SAC'；04。1438页。10.1145/967900.968188。ISBN978-1581138122。