.net - 对于只读、无序的唯一字符串集合，性能最快的选项是什么？

Question

免责声明:我意识到这个问题的完全显而易见的答案是 HashSet<string> .它的速度快得离谱，它是无序的，而且它的值是独一无二的。

但我只是想知道，因为 HashSet<T>是一个可变类，所以它有 Add , Remove ， 等等。;所以我不确定在读取操作方面，使这些操作成为可能的底层数据结构是否会牺牲某些性能——特别是，我担心 Contains .

基本上，我想知道什么是绝对的 最快 - 现有的执行数据结构可以提供 Contains类型对象的方法 string .在 .NET 框架内部或外部。

我对各种答案都感兴趣，不管它们的局限性如何。例如，我可以想象某些结构可能会被限制为特定长度的字符串，或者可能会根据问题域(例如，可能输入值的范围)等进行优化。如果存在，我想听听。

最后一件事:我并没有将其限制为只读数据结构。显然，任何读写数据结构都可以嵌入只读包装器中。我什至提到“只读”这个词的唯一原因是我对允许添加、删除等的数据结构没有任何要求。不过，如果它有这些功能，我不会提示。

更新 :

Moron's answer是我正在寻找的那种东西的一个很好的例子。 Trie * 由于以下原因，绝对看起来很有可能:HashSet<T>.Contains取决于 GetHashCode部分功能IEqualityComparer<string> , 其中, as far as I can tell , 在 .NET 中默认为 O(n)**。换句话说，字符串中的每个字符都必须检查 HashSet<string>.Contains返回 要么 true或 false .对于 Trie , 只有 true 的返回值需要 O(n) 来确定 ;返回值 false可能会更快地返回。

这当然是假设的。到目前为止，我还没有在 .NET 中编写或遇到可以击败 HashSet<string> 的 Trie 实现。在 Contains (虽然我自己写的一个实现非常接近字母“a”到“z”)。我只是说，这似乎是可能的。

*顺便说一下，那个链接也让我想到了另一个有趣/类似的可能性:DAWG .
**这里的“n”是指字符串的长度。

Answer 1

Tries适合做Contains ，特别是对于有限字母表中的字符串。给定一个字符串 s，包含在一个 trie 上的时间复杂度是 O(|s|)(|s| = s 的长度)，这是最优的。