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

Question

免责声明:我意识到这个问题的答案是完全明显的HashSet<string>.这是荒谬的快速,它是无序的,它的价值是独一无二的.

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

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

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

最后一件事:我不是将其限制为只读数据结构.显然,任何读写数据结构都可以嵌入到只读包装器中.我甚至提到"只读"这个词的唯一原因是我对数据结构没有任何要求允许添加,删除等等.如果它具有这些功能,我不会抱怨.

---

更新:

Moron的回答是我正在寻找的那种事情的一个很好的例子.一个特里*肯定似乎是一个很大的可能性,原因如下:HashSet<T>.Contains依赖于GetHashCode一些功能IEqualityComparer<string>,其中,据我可以告诉,是O(n)**默认情况下,在.NET.换句话说,在一个字符串中的每个字符必须检查HashSet<string>.Contains返回无论是true 或 false.对于a Trie,只有返回值true需要O(n)来确定 ; 返回值false可能会更快地返回.

这当然是假设的.到目前为止,我还没有编写或遇到过.NET中可以击败HashSet<string>at 的Trie实现Contains(尽管我自己编写的实现与字母'a'到'z'非常接近).我只是说,似乎有可能.

_{*顺便说一句,这个链接也让我有了另一个有趣/类似的可能性:DAWG.
**这里"n"指的是字符串的长度.}

Answer 1

除了你想知道的之外，哈希集是最快的集合。

没有更快的方法，因为底层 Hashtable 允许 O(1) 读写访问