查看“︁跳跃列表”︁的源代码

{{NoteTA
|G1 = IT
|1 = zh-cn:跳跃列表; zh-tw:跨越串列
|3 = zh-cn:列表; zh-tw:串列
}}
{{Infobox data structure
|name=跳跃列表
|type=列表
|invented_by=[[William Pugh|W. Pugh]]
|invented_year=1989
|
|space_avg=O(''n'')
|space_worst=O(''n'' log ''n'')<ref name="cs.uwaterloo">{{cite thesis |title=Skip Lists and Probabilistic Analysis of Algorithms |first=Thomas |last=Papadakis |type=Ph.D. |year=1993 |publisher=University of Waterloo |url=http://www.cs.uwaterloo.ca/research/tr/1993/28/root2side.pdf |access-date=2018-06-03 |archive-date=2017-08-10 |archive-url=https://web.archive.org/web/20170810124749/https://cs.uwaterloo.ca/research/tr/1993/28/root2side.pdf }}</ref>
|search_avg=O(log ''n'')
|search_worst=O(''n'')<ref name="cs.uwaterloo" />
|insert_avg=O(log ''n'')
|insert_worst=O(''n'')
|delete_avg=O(log ''n'')
|delete_worst=O(''n'')
}}
{{Probabilistic}}

在[[计算机科学]]中，'''跳跃列表'''是一种[[数据结构]]。它使得包含n个元素的有序[[序列]]的查找和插入操作的平均时间复杂度都是<math>O(\log n)</math>，优于[[数组]]的<math>O(n)</math>复杂度。

快速的查询效果是通过维护一个多层次的[[链表]]实现的，且与前一层（下面一层）链表元素的数量相比，每一层链表中的元素的数量更少（见右下角示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过的元素的方法可以是随机性选择<ref name="pugh">{{Cite journal| doi = 10.1145/78973.78977| title = Skip lists: A probabilistic alternative to balanced trees| journal = [[Communications of the ACM]]| volume = 33| issue = 6| pages = 668| year = 1990| last1 = Pugh| first1 = W.| authorlink1 = William Pugh| url = ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf| access-date = 2018-06-03| archive-date = 2020-06-20| archive-url = https://web.archive.org/web/20200620085929/ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf| dead-url = no}}</ref>或确定性选择<ref>{{cite conference |url=http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf |title=Deterministic skip lists |last1=Munro |first1=J. Ian |authorlink1=Ian Munro (computer scientist) |last2=Papadakis |first2=Thomas |last3=Sedgewick |first3=Robert |authorlink3=Robert Sedgewick (computer scientist) |date=1992 |publisher=Society for Industrial and Applied Mathematics, Philadelphia, PA, USA |book-title=Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92) |pages=367–375 |location=Orlando, Florida, USA |doi=10.1145/139404.139478 |conference= |access-date=2018-06-03 |archive-date=2021-05-06 |archive-url=https://web.archive.org/web/20210506124405/https://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf }}</ref>，其中前者更为常见。

== 描述 ==
[[File:Skip list.svg|thumb|400px|一张跳跃列表的示意图。每个带有箭头的框表示一个指针, 而每行是一个稀疏子序列的[[链表]]；底部的编号框（黄色）表示有序的数据序列。查找从顶部最稀疏的子序列向下进行, 直至需要查找的元素在该层两个相邻的元素中间。]]

跳跃列表是按层建造的。底层是一个普通的有序[[链表]]。每个更高层都充当下面列表的「快速通道」，这里在第<math>i</math>层中的元素按某个固定的概率<math>p</math>（通常为<math>\frac{1}{2}</math>或<math>\frac{1}{4}</math>）出现在第<math>i+1</math> 层中。每个元素平均出现在<math>\frac{1}{1 - p}</math>个列表中，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在<math>\log_{1/p} n</math>个列表中出现。

在查找目标元素时，从顶层列表、头元素起步。算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。每层链表中预期的查找步数最多为<math>\frac{1}{p}</math>，而层数为<math>\log_{1/p} n</math>，所以查找的总体步数为<math>-\frac{\log_{p} n}{p}</math>，由于<math>p</math>是常数，查找操作总体的[[时间复杂度]]为<math>\mathcal{O}(\log n)\,</math>。而通过选择不同<math>p</math>值，就可以在查找代价和存储代价之间取得平衡。

跳跃列表不像[[平衡树]]等数据结构那样提供对最坏情况的性能保证：由于用来建造跳跃列表采用随机选取元素进入更高层的方法，在小概率情况下会生成一个不平衡的跳跃列表（最坏情况例如最底层仅有一个元素进入了更高层，此时跳跃列表的查找与普通列表一致）。但是在实际中它通常工作良好，随机化平衡方案也比平衡二叉查找树等数据结构中使用的确定性平衡方案容易实现。跳跃列表在[[并行计算]]中也很有用：插入可以在跳跃列表不同的部分并行地进行，而不用对数据结构进行全局的重新平衡。

=== 实现细节 ===
{{Expand_section}}
[[File:Skip list add element-en.gif|thumb|400px|往跳跃列表中插入一个元素]]
因为跳跃列表中的元素可以在多个列表中，所以每个元素可以有多于一个指针。

跳跃列表的插入和删除的实现与普通的链表操作类似，但高层元素必须在进行多个链表中进行插入或删除。

跳跃列表的最坏时间性能具有一定随机性，但是可以通过时间复杂度为<math>\mathcal{O}(n)</math>的遍历操作（例如在打印列表全部内容时）以无随机的算法重整列表的结构，从而使跳跃列表的实际查找时间复杂度尽量符合理论平均值<math>\mathcal{O}(\log n)</math>。

除了使用无随机算法之外，我们可以以下面的准随机方式地生成每一层：

 make all nodes level 1
 j ← 1
 '''while''' the number of nodes at level j > 1 '''do'''
   '''for''' each i'th node at level j '''do'''
     '''if''' i is odd 
       '''if''' i is not the last node at level j
         randomly choose whether to promote it to level j+1
       '''else'''
         do not promote
       '''end if'''
     '''else if''' i is even and node i-1 was not promoted
       promote it to level j+1
     '''end if'''
   '''repeat'''
   j ← j + 1
 '''repeat'''

类似无随机版本，准随机重整仅在需要执行一个<math>\mathcal{O}(n)</math>操作（访问每个节点）的时候伴随进行。

==历史==

跳跃列表由{{le|威廉·普|William Pugh}}发明。{{r|pugh}}发明者对跳跃列表的评价是：“跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。”

==参见==
* [[布隆过滤器]]
* {{le|跳跃图|Skip graph}}

==参考文献==
<references/>

==外部链接==
*[http://nist.gov/dads/HTML/skiplist.html Description] {{Wayback|url=http://nist.gov/dads/HTML/skiplist.html |date=20090131102635 }} from the [[Dictionary of Algorithms and Data Structures]]
*[https://web.archive.org/web/20081018112547/http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_skl.htm skip lists] by Thomas Niemann
*[http://dsqiu.iteye.com/blog/1705530 Skip List（跳躍表）原理詳解與實現 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye技術網站] {{Wayback|url=http://dsqiu.iteye.com/blog/1705530 |date=20181118093141 }}

{{Data structures}}

[[Category:数据结构|T]]
[[Category:概率性数据结构]]