.NET 集合提供最快的搜索

Question

我有 60k 项需要根据 20k 查找列表进行检查。是否有一个集合对象（如

List

、

HashTable

）提供了异常快速的

Contains()

方法？或者我必须自己写？换句话说，默认的

Contains()

方法只是扫描每个项目还是使用更好的搜索算法。

foreach (Record item in LargeCollection)
{
    if (LookupCollection.Contains(item.Key))
    {
       // Do something
    }
}

注意。查找列表已排序。

Answer 1

在最一般的情况下，将

System.Collections.Generic.HashSet

视为默认的“包含”主力数据结构，因为评估

Contains

需要恒定的时间。

“什么是最快的可搜索集合”的实际答案取决于您的具体数据大小、有序性、哈希成本和搜索频率。

Answer 2

如果您不需要订购，请尝试

HashSet<Record>

（.Net 3.5 的新功能）

如果您这样做，请使用

List<Record>

并致电

BinarySearch

。

Answer 3

你考虑过

List.BinarySearch(item)

吗？

您说您的大量收藏已经排序，所以这似乎是一个绝佳的机会？哈希肯定是最快的，但这会带来它自己的问题，并且需要更多的存储开销。

Answer 4

您应该阅读此博客，它使用单线程和多线程技术对几种不同类型的集合和方法进行了速度测试。

根据结果，在将某些内容查找为“值”时，列表上的 BinarySearch 和 SortedList 是表现最好的，不断并驾齐驱。

当使用允许“键”的集合时，Dictionary、ConcurrentDictionary、Hashset 和 HashTable 总体表现最佳。

Answer 5

我做了一个测试：

• 第一个 - 3 个字符，包含 A-Z0-9 的所有可能组合
• 用这些字符串填充此处提到的每个集合
• 最后 - 在每个集合中搜索随机字符串并为其计时（每个集合的字符串相同）。

此测试模拟在保证有结果时的查找。

然后我将初始集合从所有可能的组合更改为仅 10,000 个随机 3 字符组合，这应该会导致随机 3 字符查找的 4.6 命中率为 1，因此这是一个不能保证结果的测试，然后再次运行测试：

恕我直言，哈希表虽然最快，但并不总是最方便的；与对象一起工作。但 HashSet 紧随其后，因此可能是值得推荐的。

只是为了好玩（你知道有趣）我运行了 168 万行（4 个字符）：

Answer 6

保持列表 x 和 y 按排序顺序。

如果 x = y，则执行你的操作，如果 x < y, advance x, if y < x, advance y until either list is empty.

该交叉点的运行时间与 min (size (x), size (y)) 成正比

不要运行 .Contains () 循环，这与 x * y 成正比，这更糟糕。

Answer 7

如果可以对项目进行排序，那么有一种比在哈希表或 B 树中进行键查找更快的方法。不过，如果你的项目不可排序，你无论如何也不能真正将它们放入 B 树中。

无论如何，如果可排序对两个列表进行排序，那么只需按顺序遍历查找列表即可。

Walk lookup list
   While items in check list <= lookup list item
     if check list item = lookup list item do something
   Move to next lookup list item

Answer 8

如果您使用 .Net 3.5，您可以使用以下方法制作更简洁的代码：

foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
  //dostuff
}

我这里没有 .Net 3.5，因此未经测试。它依赖于扩展方法。并不是说

LookupCollection.Intersect(LargeCollection)

可能与

LargeCollection.Intersect(LookupCollection)

不一样......后者可能要慢得多。

这假设 LookupCollection 是一个

HashSet

Answer 9

如果您不担心性能受到影响，那么使用 HashSet 或二分搜索的建议是可靠的。您的数据集不够大，99% 的情况下这都会成为问题。

但是，如果这只是您要做的数千次中的一次，并且性能至关重要（并且事实证明使用 HashSet/二分搜索是不可接受的），那么您当然可以编写自己的算法，在您执行操作时遍历排序列表并进行比较。每个列表最多会被遍历一次，在病理情况下不会很糟糕（一旦你走了这条路，你可能会发现比较，假设它是一个字符串或其他非整数值，将是真正的费用和优化将是下一步）。

Answer 10

如果是 .NET 8，您也可以考虑使用

System.Buffers.SearchValues<T>

https://learn.microsoft.com/en-us/dotnet/api/system.buffers.searchvalues-1?view=net-8.0