C# 中的双向 SkipList

• 下载源代码 - 11.39 KB

引言

BDSkipList 是一个通用的双向线程安全排序映射，它实现为 C# 中的一个 SkipList。它包含一个高效的子集扫描接口 IScanner/IScannable。

背景

SortedDictionary 是一个通用的集合，用于维护键值对的排序映射，同时允许快速查找任何键。但是，它的枚举器只能遍历整个排序映射，并且只能向前扫描。一旦映射变得很大，通常会需要扫描该映射的子集（给定起始/结束键），并且支持双向扫描。BDSkipList 提供了这种能力。

关于跳表结构的背景知识，请参考这篇优秀的 C# 跳表 文章或 维基百科的跳表条目。BDSkipList 的工作方式类似，但它包含两个方向的跳表，以便高效地双向扫描和查找条目。

Using the Code

从基本层面上讲，使用 BDSkipList 与使用其他集合类似。例如，以下代码将创建一个映射并插入元素，在内部保持排序。

BDSkipList<string,int> mylist = new BDSkipList<string,int>();
mylist["abc"] = 1;
mylist["def"] = 2;
mylist["ghi"] = 3; 

然后可以使用默认枚举来遍历列表中的所有元素。

foreach (KeyValuePair<string,int> kvp in mylist) {
   Console.WriteLine(" {0} = {1}",kvp.Key,kvp.Value);
} 

上述操作在标准的 SortedDictionary 上都可以以相同的方式执行。但是，IScannable 接口允许我们高效地搜索和扫描值范围。

public interface IScannable<K,V> {
   KeyValuePair<K,V< FindNext(IComparable<K> keytest,bool equal_ok);
   KeyValuePair<K,V> FindPrev(IComparable<L> keytest,bool equal_ok);
   IEnumerable<KeyValuePair<K,V>> scanForward(IScanner<K> scanner);
   IEnumerable<KeyValuePair<K,V>> scanBackward(IScanner<K> scanner);
}

使用此接口，我们可以查找样本列表中键 "b" 之后的下一个元组是 ("def" = 2)，并且我们可以高效地在 "b" 和 "z" 之间的所有键上进行双向扫描。查找操作，如 FindNext、FindPrev 以及扫描的第一个结果，对于包含 N 个元素的列表，其时间复杂度为 (log-N)，而扫描到下一个元素是 O(1)，因为它利用内部链表快速移动到下一个条目。

让我们考虑一下反向扫描所有键的代码，然后高效地正向扫描 "b" 和 "z" 之间的键子集。

// scan backwards through keys
foreach ( KeyValuePair<string,int> kvp in
   mylist.scanBackward(ScanRange<string>.All()) ) {
       Console.Writeline(" {0} = {1} ", kvp.Key, kvp.Value);
}

// scan over a subset of keys between b and z
foreach (KeyValuePair<string,int> kvp in
    mylist.scanForward(new ScanRange<string>("b","z")) {
       Console.Writeline(" {0} = {1} ", kvp.Key, kvp.Value);
} 

如果我们的列表包含数千甚至数百万个条目，这些扫描与返回的条目数量成比例，而不是与列表中的条目总数成比例，正如如果我们使用简单的 GetEnumerator 来扫描列表中的所有元素时那样。

您可能已经注意到，上面的 FindPrev 和 FindNext 使用的不是键，而是 IComparable<K> 来查找下一个条目。IScanner 的工作方式相同，这使得处理某些类型键的特殊条件变得方便。例如，可以使用特殊的 "最大键" 或 "最小键" 进行扫描。虽然对于列表的开头或结尾执行此操作可能显得微不足道，但在处理结构化键时非常有用。在一个应用程序中，键类型是一个分层的部件集，可以对 "A.B.C" 和 AfterPrefix("A.B.C") 之间的条目进行扫描。

关注点

IScanner 接口已被证明功能强大，但也偶尔不方便。例如，它总是执行包含终结点的范围扫描。虽然提供了一个 match-to 函数回调来限定条目，但这是一种不方便的方式来表达终点的包含/排除。IScanner 接口的未来版本可能会更直接地支持包含或排除的终点范围。此外，使用 IComparable<K> 的目的是为了灵活处理复合键类型的用户前缀和其他问题。然而，其功能超出了查找的有效范围。由于执行了 log-n 的初始查找，因此，start-key 必须保持对它在排序映射中位置的恒定视图非常重要。例如，如果提供的 IComparable 仅为比较返回一个随机值，则结果将非常不可预测。另一种可能性是要求扫描规范使用具有特定 LT、GT、LTE、GTE 运算符的硬键。也许未来的版本会朝着这个方向发展。

我们也可以选择不为每个方向保留一个跳表，而是保留一个方向的跳表，并在 '完整' 的跳表通道中添加双向链接。在编写时，将 FindPrev 表示为 FindNext 的镜像似乎很容易构思。实际上，不一定需要保留两个跳表。初始查找在任一跳表方向上都接近 log(n)，无论我们使用的键是什么，或者在进行初始查找后我们希望扫描的方向是什么。进行此更改将需要 FindPrev 在内部表示为 FindNext，然后回溯到前一个内部节点。也许未来的版本会执行此优化。

BDSkipList 对操作进行保守的粗粒度锁定以确保线程安全。这些锁会增加操作的开销，并且可以做得更小、更快。一种替代方法是使用 SpinLocks，在锁持有时间非常短的情况下，它们比普通锁更快。另一种替代方法是将跳表改为无锁。节点移除的方式可能在没有锁的情况下是线程安全的。移除的节点仍然指向列表，因此任何遍历已移除节点的线程都会继续到下一个节点，而不管移除发生的时间。

由于列表的枚举器是通过遍历可能变化的链表创建的，因此在枚举过程中枚举器不能保证保持不变。但是，由于节点被移除和添加的方式，枚举将安全地完成正确的扫描，无论并发发生添加或移除操作。也许枚举器为数不多的不受欢迎的特性是，如果一个枚举器在一个从列表中移除的节点上停留很长时间，当它恢复扫描时，它可能会错过在其当前节点被移除后添加到序列中的相邻节点。解决此问题的一种方法是在删除节点时将其保留在列表中，并简单地将其标记为已删除。只有当所有枚举器都释放了一个节点后，它才会被真正移除。但是，这会增加扫描、跳表维护和查找的复杂性，这些都需要特别处理被标记为已删除的节点。除非上述情况非常普遍，否则这可能不值得麻烦。

历史

• 初次发布日期：2010 年 12 月 20 日