在c# .net Compact Framework 3.5中最快的字典查找方法

Question

我希望您能够快速查找List、Set、Dictionary中是否包含特定关键字（字符串）的最快方法。我不需要在内部存储任何数据，只想知道我的关键字是否在List中。

我考虑了一些可能性，例如：

Dictionary<string, bool> myDictionary = new Dictionary<string, bool>();
if (myDictionary.ContainsKey(valueToSearch))
{
    // do something
}

但是我不需要一个值。

string[] myArray = {"key1", "key2", "key3"}
if (Array.IndexOf(myArray, valueToSearch) != -1)
{
    // do something
}

然后我发现：

List<string> list = new List<string>();
if (list.Contains(valueToSearch))    
{
    // do something
}

查找操作会经常发生，并且需要非常快速。 有没有想法来检查一个值是否等于给定的一组键中的某个键，以实现最快的速度？

- Haiperlink

---

为什么不获取RedGate Profiler的副本并自行运行一些测试呢？这将为您提供查找更快的良好指示。某些因素会影响性能，例如项目顺序、使用的算法和列表大小。我本来想这样做，但我的试用版已过期。http://www.red-gate.com/products/dotnet-development/ants-performance-profiler/ - Dustin Davis

哪种数据结构最快通常与问题的规模、数据的冗余性、查询的分布以及“垃圾”（即不匹配）查询的可能性密切相关。我们在使编译器局部变量查找表快速方面面临的问题与您在使Scrabble字典查找快速方面面临的问题是完全不同的。局部变量表很小，查询往往会聚集; Scrabble字典很大，查询很少重复。您能否更详细地描述问题的特点？ - Eric Lippert

Answer 1

在标准的集合类型中，Dictionary 是最快的，因为我认为在紧凑框架中没有 HashSet<T>。而另外两种则进行顺序搜索。

- Jim Mischel

---

我不确定我是否正确解释了MSDN，但看起来HashSet<T>包含在紧凑框架中。HashSet<T>文档 - Justin

@Justin：CF 中没有 HashSet。 - ctacke

@ctacke - 哦，现在我明白了--我看到MSDN上的“客户端配置文件”，以为是“紧凑框架”。 - Justin

@Justin - 是的，MSDN 对于 CF 支持很少是我所说的“清晰”的。 - ctacke

Answer 2

通常，像这样的问题使用字典查找是常规解决方案，只要你的键是良好的哈希值，在字典的查找表中获得相对均衡的分布。

然而，根据数据的排序方式和您要查找的内容，某些情况下列表查找可能运行得更快。

最好的方法是对每种情况进行分析，看哪种方法执行效果更好。

- Andy White

Answer 3

我同意Andy的观点。你也可以看一下SortedList，它本质上是一个按键排序的字典。如果已经排序，搜索应该会更快...

- tobias86

---

对项进行排序不会增加查找速度，因为SortedDictionary仍然使用哈希表进行查找。哈希表查找是O(1)操作。在排序列表中搜索通常是O(log n)操作。只有在哈希表存在过多冲突（意味着散列函数不足或表几乎已满）时，搜索才能优于哈希查找。 - Jim Mischel