跳表和数组有相同的限制吗？

Question

我想问一下，跳跃表和数组一样，如果在存储之前知道要存储的元素数量'n'，它们是非常高效的，对吗？

一个跳跃表的最大层数为(log n + 1)，因此在创建跳跃表之前需要知道最大层数，这意味着我应该有一个关于将要存储的元素数量的想法。

- ChrisOdney

---

跳表的一个很好的特性是最大层数可以动态增加。 - Raymond Chen

那现在不是和动态改变数组大小一样了吗？ - ChrisOdney

当涉及到跳表时，尽管重新分配的复杂度仅为对数级别，而不是数组的线性级别。一个相对较小的值 n 将涵盖所有实际情况。例如，对于 p = 0.5，n = 64 的值将足以应对64位处理器。你需要几个世纪才能生成足够的数据来填充64位地址空间。 - Raymond Chen

Answer 1

你在创建跳表时不需要知道其最大级别，只要准备好动态调整头部大小即可，头部的大小恰好为maxlevel。由于maxlevel约为log N，因此很少调整头部的大小，即使发生调整，也涉及非常少的工作量。如果你真的想避免这种情况，可以最初使用足够整个可用存储空间的容量来创建头部，尽管这样做会浪费空间，如果大多数跳表只有几百个元素。

所有这些都是因为跳表的搜索过程永远不会向上移动一级；只会向下移动。因此，插入一个新节点，其级别高于任何现有节点，不需要修改除头部之外的任何现有节点，必须修改头部以指向其最高级别的新节点。（否则，新的级别将是无用的。）

作为一个有趣的实现细节，不需要存储节点的大小；仅指向第 i 级的节点就足以证明该节点至少具有 i 级，因此从不需要将 i 与节点的大小进行比较。只需要知道头部的大小。

- rici

Answer 2

maxlevel 可以动态增加。

对于前 (2^n-1) 个节点，使用 maxlevel=2^(n-1)。当第 2^n 个节点出现时，它被分配为 level=2^n，接下来的 2^n...2^(n+1) 个节点使用 maxlevel=2^n。

- richselian