快速字符串查找的最佳集合

Question

我需要一个字符串列表以及一种快速确定该列表中是否包含字符串的方法。

为了提高查找速度，我考虑了 SortedList 和 Dictionary；然而，当我只需要一个字符串时，两者都可以使用KeyValuePair。

我知道我可以使用 KeyValuePair 并简单地忽略 Value 部分。但我确实更喜欢高效，只是想知道是否有更适合我要求的集合。

Answer 1

如果您使用的是 .NET 3.5 或更高版本，请使用 HashSet。

如果做不到这一点，Dictionary（或者您想要的 TValue 类型参数的任何类型）将比 SortedList 更快，如果你有很多条目 - 后者将使用二分搜索，因此它将是 O(log n) 查找，而不是 O(1)。

Answer 2

如果您只想知道字符串是否在集合中，请使用 HashSet

Answer 3

这听起来像是 Per MSDN 的工作

 var keys = new HashSet<string>();

：Contains 函数有 O( 1）复杂性。

但您应该注意，添加时不会出现重复错误。

Answer 4

HashSet就像一个 < code>Dictionary，但只有键。

Answer 5

如果您想滚动自己的数据结构，请使用 Trie。
http://en.wikipedia.org/wiki/Trie

最坏的情况是字符串是存在：O（字符串长度）

Answer 6

我知道这个答案对本次聚会来说有点晚了，但我遇到了我们的系统运行缓慢的问题。经过分析后，我们发现我们的数据结构结构化方式发生了大量字符串查找。

因此我们做了一些研究，遇到了这些基准测试，做了我们自己的测试，现在已经改用 SortedList。

if (sortedlist.ContainsKey(thekey))
{   
//found it.
}

尽管事实证明字典速度更快，但我们需要重构的代码更少，而且性能的提高对我们来说已经足够好了。

无论如何，想分享该网站，以防其他人遇到类似的问题。它们在数据结构之间进行比较，其中您要查找的字符串是“键”（如哈希表、字典等）或“值”（列表、数组或字典等），这就是我们的字符串所在的位置存储。

Answer 7

我知道这个问题已经很老了，但我只需要解决同样的问题，只是针对一小部分字符串（2 到 4 之间）。

就我而言，我实际上对字符串数组进行了手动查找，结果比 HashSet（我对其进行了基准测试）要快得多。

for (int i = 0; i < this.propertiesToIgnore.Length; i++)
{
    if (this.propertiesToIgnore[i].Equals(propertyName))
    {
        return true;
    }
}

请注意，它比仅适用于小型数组的哈希集更好！

编辑：仅适用于手动 for 循环，不使用 LINQ，注释中详细信息