免责声明:我意识到这个问题的完全显而易见的答案是HashSet<string>
。它的速度快得离谱,它是无序的,它的值是独一无二的。
但我只是想知道,因为HashSet<T>
是一个可变类,所以它有Add
,Remove
等;所以我不确定使这些操作成为可能的底层数据结构在读取操作时是否会牺牲某些性能 - 特别是,我关心Contains
.
基本上,我想知道现有的可以为 type 对象提供方法的绝对最快的数据结构是什么。在 .NET 框架本身内部或外部。Contains
string
我对各种答案感兴趣,不管它们有什么限制。例如,我可以想象某些结构可能仅限于特定长度的字符串,或者可能会根据问题域(例如,可能的输入值的范围)等进行优化。如果存在,我想听听。
最后一件事:我并没有将其限制为只读数据结构。显然,任何读写数据结构都可以嵌入到只读包装器中。我什至提到“只读”这个词的唯一原因是我对允许添加、删除等的数据结构没有任何要求。不过,如果它具有这些功能,我不会抱怨。
更新:
Moron 的回答是我正在寻找的那种东西的一个很好的例子。Trie * 绝对看起来很有可能,原因如下:HashSet<T>.Contains
取决于GetHashCode
some 的功能,IEqualityComparer<string>
据我所知,在 .NET 中默认为 O(n)**。换句话说,必须检查字符串中的每个字符以HashSet<string>.Contains
返回or。对于 a ,只有一个返回值需要 O(n) 来确定; 的返回值可能会更快地返回。true
false
Trie
true
false
这当然是假设的。到目前为止,我还没有在 .NET 中编写或遇到可以击败 a HashSet<string>
at的 Trie 实现Contains
(尽管我自己编写的实现非常接近字母表 'a' 到 'z')。我只是说,这似乎是可能的。
*顺便说一句,那个链接也让我想到了另一个有趣/类似的可能性:DAWG。
**这里的“n”是指字符串的长度。