C# 中的 Skip List
4.94/5 (79投票s)
Skip Lists，它们的算法，以及 C# 中的 SkipList 类。
引言
Skip Lists 是平衡树的替代方案。它由 William Pugh 发明，是一种使用概率算法来保持结构平衡的数据结构。Skip Lists 的算法非常简单且优雅。Skip Lists 的速度也非常快。这些优点使其成为其他数据结构的有吸引力的替代方案。
在本文中，我将描述 Skip Lists 是什么，并用伪代码展示它们的算法。伪代码直接来自 William Pugh 的论文，可以在 此处 找到。
Skip List 结构
Skip Lists 由一系列相互连接的节点组成。每个节点包含一个键/值对以及一个或多个指向列表中后续节点的引用或指针。每个节点包含的引用数量是随机确定的。这赋予了 Skip Lists 概率性，并且节点包含的引用数量称为其节点级别。
每个节点至少有一个节点引用，第一个引用总是指向列表中的下一个节点。从这个意义上说，Skip Lists 非常类似于链表。然而，任何额外的节点引用都可以跳过一个或多个中间节点，并指向列表后面的节点。这就是 Skip Lists 得名的由来。
Skip List 中始终存在的两个节点是头节点（header node）和 NIL 节点。头节点标记列表的开头，NIL 节点标记列表的结尾。NIL 节点是唯一的，因为它在创建 Skip List 时，会给它一个大于 Skip List 中任何合法插入键的值。这对于 Skip Lists 算法的工作方式很重要。
Skip Lists 还有三个重要属性：最大级别（maximum level）、当前整体级别（current overall level）和概率（probability）。最大级别是 Skip List 中节点可能拥有的最高级别。换句话说，最大级别是 Skip List 节点可能拥有的指向其他节点的引用的最大数量。当前整体级别是 Skip List 中具有最高级别的节点的级别值。概率是用于为每个节点随机确定级别的算法中的一个值。
包含多个节点的 Skip List。
确定节点级别
每个节点的级别使用以下算法确定
randomLevel()
lvl := 1
--random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvl
其中 `p` 是 Skip List 的概率值，`MaxLevel` 是 Skip List 中任何节点允许的最大级别。
节点级别初始化为 1。每次 `while` 循环执行时，级别值会增加 1。如果 `p` 设置为 0.5，则 `while` 循环执行一次的概率是 50%，执行两次的概率是 25%，执行三次的概率是 12.5%。这创建了一种结构，其中低级别的节点比高级别的节点多。
这里有优化空间。假设 Skip List 的整体级别是 4，并且 `randomLevel` 算法为新节点返回 7。由于 7 大于 4，新的 Skip List 级别将是 7。然而，7 比 4 高 3 个级别。这意味着在搜索 Skip List 时，将有 2 个额外的级别需要不必要地遍历（当我们检查搜索算法时，这一点会更清楚）。我们需要一种方法来限制 `randomLevel` 算法的结果，使其永远不会产生比当前 Skip List 整体级别多一级的级别。Pugh 建议“固定骰子”。这是修改后的 `randomLevel` 算法
randomLevel(list)
lvl := 1
--random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel and lvl <= list->level do
lvl := lvl + 1
return lvl
搜索
在 Skip List 中搜索键，首先从整体列表级别的头节点开始，并在列表中向前移动，将节点键与搜索键进行比较。如果节点键小于搜索键，则搜索继续在同一级别向前移动。如果节点键等于或大于搜索键，则搜索下降一个级别并继续向前移动。这个过程一直持续到找到搜索键（如果存在于 Skip List 中）。如果不存在，搜索将继续到列表末尾，或者直到找到第一个值大于搜索键的键。
Search(list, searchKey)
x := list->header
--loop invariant: x->key < searchKey
for i := list->level downto 1 do
while x->forward[i]->key < searchKey do
x := x->forward[i]
--x->key < searchKey <= x->forward[1]->key
x := x->forward[1]
if x->key = search then return x->value
else return failure
其中 `forward` 是每个节点指向列表中后续节点的节点引用数组。
搜索键值为 8。
插入
插入始于搜索 Skip List 中插入新键/值对的位置。搜索算法使用一个更改：添加了一个节点数组来跟踪搜索中下降到较低级别的 Skip List 中的位置。这是因为当新节点插入 Skip List 时，这些节点中的指针需要重新排列。
Insert(list, searchKey, newValue)
local update[1..MaxLevel]
x := list->header
--loop invariant: x->key < searchKey
for i := list->level downto 1 do
while x->forward[i]->key < searchKey do
x := x->forward[i]
--x->key < searchKey <= x->forward[1]->key
update[i] := x
x := x->forward[1]
if x->key = search then x->value := newValue
else
lvl := randomLevel()
if lvl > list->level then
for i := list->level + 1 to lvl do
update[i] := list->header
list->level := lvl
x := makeNode(lvl, searchKey, newValue)
for i := 1 to lvl do
x->forward[i] := update[i]->forward[i]
update[i]->forward[i] := x
此算法的第一部分应该很熟悉。它与搜索算法相同，只是它使用 `update` 数组来保存搜索下降到较低级别的节点引用。搜索结束后，会检查搜索停止的节点中的键是否与搜索键匹配。如果匹配，则用新值替换该键的值。如果键不匹配，则创建一个新节点并将其插入 Skip List。
要插入一个新节点，会从 `randomLevel` 算法获取一个节点级别。如果此值大于 Skip List 的当前整体级别，则 `update` 数组中从 Skip List 整体级别到新级别的引用将被赋值为指向头节点。这样做是因为如果新节点具有比 Skip List 当前整体级别更高的级别，则头节点中的前向引用将需要指向这个新节点，而不是 NIL 节点。此重新分配发生在算法的下一步。
接下来，新节点被实际创建，并在下一个 `for` 循环中被“切入”到 Skip List 中。这个循环的作用是从 Skip List 的底部开始，一直到新节点的级别，在此过程中重新分配前向引用。这非常类似于在链表中插入新节点时重新排列引用，只是对于 Skip List，需要重新分配的是一个引用数组，而不是一两个引用。
插入键 10 之前的 Skip List。
插入键 10 之后的 Skip List。
删除
删除使用与插入相同的搜索算法；它会跟踪搜索中下降到较低级别的列表中的每个位置。如果找到要删除的键，则会删除包含该键的节点。
Delete(list, searchKey)
local update[1..MaxLevel]
x := list->header
--loop invariant: x->key < searchKey
for i := list->level downto 1 do
while x->forward[i]->key < searchKey do
x := x->forward[i]
--x->key < searchKey <= x->forward[1]->key
update[i] := x
x := x->forward[1]
if x->key = searchKey then
for i := 1 to list->level do
if update[i]->forward[i] != x then break
update[i]->forward[i] := x->forward[i]
free(x)
while list->level > 1 and
list->header->forward[list->level] = NIL do
list->level := list->level - 1
找到键后，`for` 循环从 Skip List 的底部开始到顶部，将指向即将删除的节点的引用重新分配给紧随其后的节点。同样，非常类似于链表，只是这里需要管理指向列表中后续节点的引用数组。
完成此操作后，节点将被删除。唯一剩下要做的是在必要时更新整体当前列表级别。这在最后的 `while` 循环中完成。
删除键 9 之前的 Skip List。
删除键 9 之后的 Skip List。
C# 实现
William Pugh 的 Skip List 的 C# 实现实现了 `IDictionary` 接口。任何可以使用 `IDictionary` 的地方，都可以使用此版本的 Skip List。
在几个地方我偏离了上面描述的算法。首先，正如你可能已经注意到的，算法使用的是基 1 数组而不是基 0。这对于 C# 实现来说必须更改，但并不难。其次，更重要的是，我取消了 Skip List 必须用最高可能键初始化的要求。我通过移除 NIL 节点并将头节点作为 Skip List 的开始和结束来做到这一点。这稍微复杂化了算法，并因此使其变慢。但是，我认为这是一个值得做出的权衡，因为在我看来，要求客户端事先知道将使用的最高可能键是一种不必要的负担。
演示应用
我创建了两个演示应用程序。一个只是允许你对 Skip List 执行 `IDictionary` 和 `ICollection` 操作。这个应用程序允许你直接执行操作。也就是说，它不会阻止你做会导致异常的事情。这是故意的。我想表明 `SkipList` 类按照 `IDictionary` 和 `ICollection` 规范执行，包括在某些事件发生时抛出异常，例如尝试在使用已修改的 `SkipList` 后使用现有的枚举器。当然，该应用程序会捕获这些异常并显示错误消息。
第二个应用程序通过允许你按正向、反向或随机顺序插入多达一百万个项目来压力测试 `SkipList` 类。它会返回计时结果。它还允许你搜索任何项目。作为比较，我包含了 .Net Framework 的 `SortedList` 类。你可以对两个类执行相同的操作并比较结果。我选择 `SortedList` 类的原因是它在目的上似乎最接近 `SkipList` 类。
这里有一个说明：在大多数情况下，`SkipList` 类比 `SortedList` 类性能好得多。我包含了代码，以便在实际插入对象之前，修改 `SortedList` 对象的 `Capacity` 属性以匹配插入的项目数。我的想法是，这会让事情更公平，甚至可能使 `SortedList` 类占据优势，但事实并非如此。
演示 zip 文件包含一个 Visual C# 解决方案，其中有三个项目。一个项目是 SkipList 本身，另一个项目是 SkipList 演示，最后一个项目是 `SkipList` 压力测试。为了减小文件大小，我删除了每个项目中的 `bin` 和 `obj` 文件夹。这意味着你需要从头开始构建解决方案，然后选择 SkipListDemo 项目或 SkipListStressTest 项目作为启动项目。你可以通过在解决方案资源管理器中右键单击项目并选择“设置为启动项目”来做到这一点。
希望你发现这个类很有用。欢迎所有评论。谢谢！