我有60,000个项目需要与20,000个查找列表进行匹配。是否有一种集合对象（例如List，HashTable），它提供了异常快速的Contains()方法？还是我必须编写自己的代码？换句话说，默认的Contains()方法只是扫描每个项目，还是使用更好的搜索算法。
foreach (Record item in LargeCollection)
{
if (LookupCollection.Contains(item.Key))
{
// Do something
}
}
注意。查找列表已经排序。
在最一般的情况下，将 System.Collections.Generic.HashSet 视为默认的“包含”工具数据结构，因为它需要恒定时间来评估 Contains。
“最快的可搜索集合是什么”这个问题的实际答案取决于您的具体数据大小、有序性、散列成本和搜索频率。
HashSet<Record>（.Net 3.5中新增）。List<Record>并调用BinarySearch。您考虑过使用List.BinarySearch(item)吗？
您说您的大型集合已经排序，因此这似乎是一个完美的机会？哈希肯定是最快的，但这也带来了自己的问题，并需要更多的存储开销。
你应该阅读这篇博客，它对多种不同类型的集合和方法进行了速度测试，并使用单线程和多线程技术。
根据结果，在查找“值”时，List和SortedList上的BinarySearch始终是表现最好的。
当使用允许“键”的集合时，Dictionary、ConcurrentDictionary、Hashset和HashTables总体表现最佳。
此测试模拟了在有保证有结果的情况下进行查找。
然后，我将初始集合从所有可能的组合更改为仅包含10,000个随机3个字符组合，这应该产生1/4.6的随机3字符查找命中率，因此这是一项没有保证结果的测试，并再次运行了测试：
我认为HashTable虽然速度最快，但不总是最方便的；使用对象工作时HashSet非常接近，可能是要推荐的方法。
只是为了好玩（你知道FUN），我尝试了1.68M行（4个字符）：
保持列表x和y的排序。
如果x = y，则执行您的操作，如果x < y，则将x前进，如果y < x，则将y前进，直到任一列表为空。
此交集的运行时间与min（size（x），size（y））成比例。
不要运行.Contains()循环，这是与x * y成比例的，这更糟糕。
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
foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
//dostuff
}
我这里没有 .Net 3.5，所以这个还没有测试。它依赖于一个扩展方法。注意，LookupCollection.Intersect(LargeCollection) 可能与 LargeCollection.Intersect(LookupCollection) 不同...后者可能会慢得多。
这假设 LookupCollection 是一个 HashSet。