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

Question

我需要一个字符串列表，并且需要一种快速确定一个字符串是否在该列表中的方法。

为了增强查找速度，我考虑使用SortedList和Dictionary；但是，这两个都需要使用KeyValuePair，而我只需要单个的string。

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

- Jonathan Wood

Answer 1

如果你使用的是.NET 3.5或更高版本，请使用HashSet<String>。

如果无法使用，使用Dictionary<string, byte>（或任何你想要的TValue类型参数）比SortedList更快，如果有很多条目-后者将使用二进制搜索，因此它将是O(log n)查找，而不是O(1)。

- Jon Skeet

---

@Jonathan：同意 - 这就是生活。在.NET 4中，有一个接口来表示集合（ISet<T>），还有另一个选项SortedSet<T>（在这种情况下也不是特别有用）。 - Jon Skeet

我刚才回头看了一下。O(1)的查找确实很快。但是，我猜这个集合实现了某种哈希。因此，O(1)假设没有冲突吗？ （顺便说一下，我正在学习你的书。） - Jonathan Wood

@Jonathan：如果哈希合理，那么它的时间复杂度是O(1)，因此不会有太多冲突。 - Jon Skeet

Answer 2

如果你只是想知道一个字符串是否在集合中，可以使用 HashSet<string>。

- BrokenGlass

Answer 3

这听起来像是一项工作。

 var keys = new HashSet<string>();

根据MSDN，Contains函数的复杂度为O(1)。

但是需要注意的是，当添加重复项时，它不会报错。

- H H

---

更加准确地说，Add方法不会抛出异常，但如果键已经存在，则返回false；如果添加成功，则返回true。 - Alois Kraus

Answer 4

HashSet<string>类似于Dictionary，但它只包含键值。

- Albin Sunnanbo

Answer 5

我知道这个问题非常老，但是我必须解决同样的问题，只针对非常少量的字符串（在2到4之间）。

在我的情况下，我实际上使用了手动查找字符串数组的方法，这比HashSet<string>要快得多（我进行了基准测试）。

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

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

编辑：仅在手动for循环中使用，不要使用LINQ，在评论中有详细说明。

- Artur Krajewski

---

是的，HashSet<> 有一些开销。我只会建议在搜索较大的集合时使用它。顺便说一下，您的代码可以缩短为类似于 return PropertiesToIgnore.Any(p => p.Equals(propertyName)) 的形式。 - Jonathan Wood

不幸的是，使用Linq会使执行速度减慢10倍！基准测试结果为ArrayManualLoop: 6.018 ns ArrayLinq: 59.171 ns。Linq会破坏处理器缓存，所有可能的收益都会丧失。 - Artur Krajewski

Answer 6

我知道这个答案来得有点晚，但是我们遇到了系统运行缓慢的问题。经过分析，我们发现由于数据结构的设计方式存在大量的字符串查找操作。

因此，我们进行了一些研究，发现了这些基准测试，进行了自己的测试，并现在已经切换到使用 SortedList。

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

尽管字典证明更快，但我们需要重构的代码更少，而且性能提高已经足够好了。无论如何，我想分享这个网站，以防其他人遇到类似的问题。他们对数据结构进行比较，其中你要查找的字符串是“键”（如HashTable、Dictionary等），或者在“值”（List、Array或Dictionary等）中存储，这就是我们存储的方式。

- user3810913

Answer 7

如果你想自己实现数据结构，可以使用 Trie。 http://en.wikipedia.org/wiki/Trie 最坏情况是字符串存在：O（字符串长度）

- James