什么.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

我一起做了一个测试：

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

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

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

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

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

Answer 5

您应该阅读此博客,该博客使用单线程和多线程技术快速测试了几种不同类型的集合和方法.

根据结果​​,列表中的二进制搜索和SortedList是在将某些东西视为"价值"时不断进行的最佳表现.

当使用允许"键"的集合时,Dictionary,ConcurrentDictionary,Hashset和HashTables整体表现最佳.