玻尔百科在计算机科学领域，对海量有序数据进行高效搜索是一项基础性挑战。简单的有序链表虽然概念上易于理解，但其线性的、逐一进行的搜索方式，在数据集增长时会变得极其缓慢。虽然像平衡树这样的复杂结构提供了高效的对数时间解决方案，但它们通常伴随着高昂的实现复杂度和错综复杂的再平衡规则。这就为一种既高效又简洁的数据结构留下了知识上的空白。
跳表正是针对这一问题的杰出解决方案。它是一种概率性数据结构，巧妙地在基础链表之上构建了一个多层次的“高速公路”系统，从而达到了与平衡树同样理想的对数搜索时间，但方法却更为简单和灵活。本文将引导您领略跳表的精妙之处。首先，在“原理与机制”部分，我们将探讨该结构如何利用随机性来构建其层级，以及其分层搜索算法的工作原理。接着，在“应用与跨学科联系”部分，我们将看到跳表的实际应用，审视其在解决内存管理等工程问题中的强大作用，以及它与社会网络结构之间深刻而出人意料的联系。
想象一条非常非常长的街道，街道两旁是房屋，每栋房屋都按完美的升序编号。你的任务是找到一栋特定的房屋，比如 7428 号。唯一的规则是你必须从 1 号房屋开始，沿着街道走下去，逐一检查每栋房屋的门牌号。如果有一万栋房屋，这将是一段漫长而乏味的步行。这恰恰是计算机科学中简单有序链表所面临的情况。它是一个有序的元素集合，但要找到任何一个特定元素，你可能需要遍历列表的大部分。在这种结构中进行搜索，平均耗时与元素数量 成正比。对于大型集合，这种线性的 时间实在是太慢了。
在现实世界中我们如何解决这个问题？我们修建高速公路。高速公路的入口有限，让你能够绕过大段的普通道路。你可以沿着高速公路巡航，直到接近你的出口，然后再下到普通道路完成最后一段路程。这便是跳表背后卓越的核心思想。
跳表在基础的有序列表之上构建了一个“快速通道”的层级结构。最底层的第 0 层是我们最初的“普通道路”，包含每一个元素。第 1 层是一条快速通道，只包含这些元素的一个子集。第 2 层是一条更高级的快速通道，包含第 1 层元素的一个子集，依此类推。
但这引出了一个关键问题：我们如何决定哪些房屋可以设置通往高速公路的入口？我们可以设计一个复杂的、确定性的方案来确保入口间距完美，但这通常会导致添加或移除房屋的规则变得复杂。跳表的精妙之处在于它放弃了僵化的计划，转而拥抱概率的力量。
当我们将一个新元素添加到列表中时，我们会问：它应该被放在第 1 层吗？我们抛一枚硬币。如果是正面（“成功”事件，以某个概率 发生，通常为 ），我们就建一个入口——该元素在第 1 层获得一个节点。然后我们再问：它也应该被放在第 2 层吗？我们再抛一枚硬币。我们持续这个过程，不断将元素向上提升，直到我们得到一个反面。一个节点的“高度”就是它出现的层数。
这个过程之所以优美，是因为它是完全去中心化的。一个新节点的高度是当场决定的，无需任何关于其他节点的信息。然而，这个简单的随机过程却能产生一个极其高效的结构。我们可以分析其成本。对于 个元素中的每一个，它所需要的指针数的期望值是其出现在各层概率的总和：。这是一个几何级数，其和为 。因此，根据期望的线性性质，整个结构中指针总数的期望值就是 。如果我们选择 ，我们期望总共只使用 个指针。以适度的内存代价，我们就构建了一个复杂的多层交通网络。
现在我们有了高速公路系统，如何用它来找到一个地址呢？你不会从缓慢的普通道路开始。你会走上最高、最快的可用高速公路。跳表的搜索算法正是这样做的：
最终，你会到达最底层的第 0 层。在这条普通道路上进行最后一段短距离的遍历，就能将你精确定位到正确的位置。这个搜索过程是一个贪心算法能够奏效的绝佳范例。在每一步，你都在做出最佳的局部选择——尽可能地停留在最快的车道上——而这最终导向了全局最优路径。其逻辑非常清晰，可以用一个简单的不变性来描述：在搜索过程中的任何时刻，当前节点都是其键值仍然小于目标键值的最右侧的可能节点。
为什么这个过程如此之快？让我们直观地思考一下。对于一个提升概率 ，每一层的大小期望约为其下一层的 倍。如果 ，向上移动一层就好比将“出口”的数量减半。这与二分搜索的基本逻辑是相同的。将一个包含 个元素的列表减半的次数大约是 。这意味着你需要导航的总层数与 成对数关系 [@problem_d:3263277]。
那么我们在每一层要走多少步呢？平均来说，是一个常数。想象一下反向的搜索路径：从目标向上攀升。在任何一层，一个节点有 的概率是来自上一层的。在找到一个有匝道通往上一层的节点之前，你期望检查的节点数是一个常数 。所以，一次搜索的总期望成本是层数乘以每层的成本：。对于计算机科学家来说，这就是搜索的圣杯： 的期望时间。
现在，一个科学家必须诚实地对待他的工具。跳表是一种随机化算法，其性能是一种概率性保证。搜索有没有可能很慢？有。在一次宇宙级的超级坏运气事件中，每一次抛硬币的结果都可能是反面。这将意味着没有高速公路被建成；跳表退化成一个单一、缓慢的链表。搜索将退化为痛苦的 线性扫描。但这种最坏情况的概率是多少？对于 ，它是 ，一个比你能想象的任何速度都更快地变得小到可以忽略不计的数字。
事实上，我们可以做出比“平均情况下很快”更强的陈述。我们可以证明搜索时间以高概率是 。这是一个具有强大意义的技术术语：你的搜索时间显著长于 的几率小于 ，对于任何你关心的常数 。这是一个极其有力的保证，使得跳表在实践中成为一个可靠且稳健的选择，。
跳表的真正优雅之处不仅体现在其理论上，更在于其实际实现中。它是算法工程的杰作。
首先，它的结构异常灵活。构成链表的“指针”是一个抽象概念。它们可以是直接的内存地址，但同样也可以是大型数组中的整数索引，这在某些编程环境中是一个有用的特性。该结构也易于增强。如果你需要高效地向后遍历，只需通过添加“前驱”指针，将每一层的列表都变成双向链表即可。
然而，在当今多核处理器的时代，跳表的杀手级特性是它对并发性的天然亲和力。大多数平衡搜索树，如久负盛名的红黑树或其随机化表亲——树堆，都依赖于复杂的“旋转”操作来维持平衡。一次插入可能会触发一系列影响到树根的指针变化。这为并发操作造成了“交通堵塞”，因为结构的大部分必须被锁定。
跳表的更新则截然不同。一次插入或删除只需要在几个局部位置进行节点的缝合或解开，每一层的列表中各一次。这种局部性对于并行编程来说是天赐之物。并发删除的算法尤其优美：要删除一个节点，你首先执行一个快速的原子操作，将该节点标记为“逻辑删除”。然后，在一个悠闲的、独立的清理步骤中，你再将它从列表中物理地断开链接。这种两阶段的“懒惰删除”方法优雅地回避了并发数据结构设计中许多最棘手的问题，使得跳表成为现存最有效和最广泛使用的并发有序字典之一。
跳表利用简单、局部、随机的选择来创造一个强大、高效且全局一致的结构，它证明了概率与计算机科学结合所能产生的意想不到的美。
既然我们已经探索了跳表的内部机制，即其概率与指针的优雅之舞，我们可以提出一个真正触及任何科学思想核心的问题：“所以呢？”这种结构有什么用？它仅仅是一个课堂上的奇特玩意儿，一种平衡树的巧妙替代品，还是它揭示了关于计算和世界的更深层次的东西？
你会欣喜地发现，答案是，跳表远不止一个简单的字典。它是解决复杂工程问题的蓝图，是反映我们硬件物理约束的一面镜子，而且最令人惊讶的是，它是支配我们如何在自己的社交世界中导航的一个基本原则的美丽数学回响。让我们踏上一段旅程，去看看跳表的实际应用，去见证它的力量、它的局限，以及它与其他科学领域的深刻联系。
想象你正在设计一个操作系统，也就是计算机资源的数字政府。你最关键的任务之一是管理这个城市的“土地”——它的内存。程序不断地请求不同大小的地块（内存块），使用它们，然后归还它们。作为城市规划师，你的工作是跟踪所有空闲的地块（“空闲列表”），以便为下一个请求高效地找到一个合适的地块。
一个常见的策略是“最佳适配”：为了满足一个大小为 的请求，你找到大小至少为 的最小可用地块。这样可以最大限度地减少空间浪费。但这产生了一个令人望而生畏的双重记账问题。你需要按大小搜索你的空闲列表，但当一个块被归还时，你需要按地址找到它的邻居，看看你是否可以将相邻的空闲地块合并成一个更大的地块——这个过程称为合并。
你如何能够同时高效地维护两种不同的排序顺序？对于其中一项任务，简单的数组或链表会非常慢。在这里，跳表展示了它不仅仅是一种数据结构，更是一种多功能的组织工具。我们可以使用两个跳表。一个跳表按大小组织空闲块，从而可以以闪电般的对数时间搜索最佳适配块。第二个跳表按起始地址组织相同的空闲块。这使我们也能在对数时间内找到一个新释放块的邻居，从而使合并变得高效。这种双跳表架构为几乎所有现代计算机系统核心的一个真正难题提供了一个优雅且高性能的解决方案。
管理动态集合的同样原则也适用于其他地方。跳表可以构成一个非常简单的优先队列，这是一种对调度任务或模拟事件至关重要的结构。“最重要”的项（键值最小的项）始终是基础列表的第一个元素，可以在常数时间内访问。移除它并找到下一个最小值是一次标准的跳表删除操作，速度很快。这使得跳表在实现优先队列方面，成为经典二叉堆的有力竞争者，尤其是在像大规模外部排序这样的算法中，我们需要在一个称为 路合并的过程中，从 个不同的有序列表中反复找到 个元素中的最小值。
到目前为止，我们的旅程一直将计算视为一个抽象的数学过程。但算法运行在物理机器上，在这些机器上，物理定律——或者至少是硬件工程的现实——会发挥作用。其中最基本的一个现实是，访问内存不是瞬时的，并且并非所有内存访问都是平等的。现代处理器使用一个缓存层级——一些小型的、极快的内存库，用于存储最近使用过的数据。访问已经在缓存中的数据（一次“命中”）比从主存中获取它（一次“未命中”）要快几个数量级。
这正是跳表最大的优势——其灵活的、基于指针的特性——可能成为其阿喀琉斯之踵的地方。跳表中的每个节点通常被分配为一小块独立的内存，可能随机散布在主存的广阔空间中。在跳表中搜索涉及“指针追逐”，即从一个节点跳到下一个节点。以高概率，每次跳跃都会落在一个不同的、非连续的内存区域，从而引发一次昂贵的缓存未命中。
让我们来量化这一点。在一个精心构建的分析中，人们可以将跳表搜索与“缓存无关”结构的搜索进行比较——这种设计在不了解缓存任何具体细节的情况下，以最大化局部性的方式在内存中布局数据。对于搜索 （约 1600 万）个项目，且典型内存块大小为 的情况，跳表预计会产生约 次 I/O 操作（缓存未命中）。而理论上最优的缓存无关结构仅需 次 I/O 操作即可完成相同的搜索。两者之比达到了惊人的 12 倍。
这并不意味着跳表是一个糟糕的结构；它只是意味着存在权衡。在内存局部性至关重要的场景中，一个基于数组的结构，如使用开放地址法的哈希表，其性能可能会超过基于跳表的结构，即使跳表在抽象模型中具有更好的渐进复杂度。在连续数组中大步前进的缓存友好性，可能会压倒指针追逐的对数级优雅。数据结构的选择是一项工程决策，是算法理论与物理现实之间的妥协。
基本的跳表是为了速度而构建的，但如果我们想要的不仅仅是快速搜索呢？如果我们想知道一个元素的排名，或者找到列表中的第 小的项呢？标准的跳表就像一个没有站号的快速列车系统；你可以快速地在站点之间穿梭，但你不知道哪个是线路上的第 5 站或第 10 站。
跳表的优美之处在于它可以被增强。我们可以在每个前向指针上添加一个“跨度”或“宽度”，存储该快速通道链接“跳过”了多少个基础层节点。通过这个简单的补充，跳表就得到了转变。要找到第 个元素，你从顶层开始并记录你的排名。在每一步，你查看下一个指针的跨度。如果向前跳跃不会让你超过排名 ，你就进行跳跃，并将跨度加到你的当前排名总数上。通过在下降层级时重复此过程，你可以在对数时间内定位到第 个元素，就像进行普通搜索一样。跳表变成了一个“可索引”的结构，融合了链表的快速更新和数组的随机访问能力。
这种增强的思想可以更进一步。标准跳表使用固定的概率 来提升节点。在对数据一无所知的情况下，这工作得非常好。但如果我们知道一些信息呢？想象一个数据集，其中某些区域数据点密集，而其他区域则稀疏。在所有地方以相同的频率建造快速通道似乎是一种浪费。直观上，我们希望在稀疏的、“长距离”区域建造更多的快速通道，而在密集的、“局部”集群中建造得少一些。
我们可以让跳表成为一个智能的、自适应的结构。我们可以为每个节点定义一个局部的提升概率 ，而不是使用固定的 ，这个概率基于数据的局部密度。在键值之间差距较大（低密度）的地方，我们设置一个较高的 ，增加构建长程快速链接的机会。在差距较小（高密度）的地方，我们使用一个较低的 。我们甚至可以使每一层的水平搜索变为“插值引导”，利用键的值来预测我们的目标可能在哪里，而不仅仅是一步一步地前进。这就创造了一种由其所持有的数据本身塑造的数据结构，这是分布敏感设计的一个美丽范例。
我们在本章开始时曾暗示，跳表与一个远超计算机科学范畴的概念有关。现在让我们揭示这一联系。在 20 世纪 60 年代，社会学家 Stanley Milgram 进行了一项著名的实验，催生了“六度分隔理论”这一短语。他表明，在美国的任意两个人都可以通过一小串社会熟人链联系起来。这被称为“小世界现象”。
这怎么可能呢？网络科学家发现，像我们的社交网络这样的网络具有一种非常特殊且强大的结构：它们由高度的局部聚类（你的朋友们很可能彼此认识）和少数随机的长程快捷方式（一个搬到另一个国家的朋友）所定义。正是这些快捷方式防止了世界成为一个巨大、脱节的空间，而是使其变得“小”且易于导航。
现在再来看看跳表的结构。在它的基础，即第 0 层，我们有完美的局部聚类：每个节点都与其直接邻居相连。由随机提升的节点构成的更高层，恰恰形成了定义小世界网络的那种长程快捷方式。在跳表中进行搜索，就是在这个网络中进行贪心导航。算法很简单：采取你能采取的最长跳跃而不越过你的目标，然后重复。这正是在社交网络中，信息（如 Milgram 的信件）被认为高效传播的方式。
跳表，本质上是计算机科学家对小世界原则的形式化。我们从概率论证中推导出的期望对数搜索时间，是与“六度分隔理论”相对应的数学概念。这种深刻而出人意料的统一性——在一种用于排序数据的算法和一种社会结构理论之间——证明了基本思想的力量。它表明，高效导航的原则是普适的，无论被导航的世界是由人还是由数据构成。这种“快捷方式”原则如此强大，以至于它甚至可以被嫁接到其他数据结构上，例如数据库中使用的 B+ 树，以创造出有趣的混合设计。
从管理计算机内存到反映人类社会结构，跳表被证明是一种丰富、强大且富有深刻见解的思想，是算法世界中意想不到的美与统一的光辉典范。