5

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

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

基本上，我想知道现有的可以为 type 对象提供方法的绝对最快的数据结构是什么。在 .NET 框架本身内部或外部。Containsstring

我对各种答案感兴趣，不管它们有什么限制。例如，我可以想象某些结构可能仅限于特定长度的字符串，或者可能会根据问题域（例如，可能的输入值的范围）等进行优化。如果存在，我想听听。

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

更新：

Moron 的回答是我正在寻找的那种东西的一个很好的例子。Trie * 绝对看起来很有可能，原因如下：HashSet<T>.Contains取决于GetHashCodesome 的功能，IEqualityComparer<string>据我所知，在 .NET 中默认为 O(n)**。换句话说，必须检查字符串中的每个字符以HashSet<string>.Contains返回or。对于 a ，只有一个返回值需要 O(n) 来确定; 的返回值可能会更快地返回。true falseTrietruefalse

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

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

4

4 回答 4

2

尝试对于做 a 很有好处Contains，尤其是对于来自有限字母表的字符串。给定一个字符串 s，在 trie 上包含的时间复杂度是 O(|s|) (|s| = s 的长度)，这是最优的。

于 2010-06-17T17:33:31.703 回答
1

哈希表为查找摊销 O(1)。没有比这更好的了，O(1/n) 算法是永动机。只有两件事使他们表现不佳：

  • 导致许多冲突的不良散列函数。最糟糕的情况会退化到 O(n) 的查找。字符串不会有任何问题，它们的哈希值非常好。String.GetHashCode() 做得非常好。
  • 一个严重变异的集合，其中包含许多早期添加的已删除项目。这会导致许多需要被迭代器跳过的空哈希桶。降级到 O(n) 在技术上是可能的，尽管非常罕见。一个简单的解决方法是通过重新分配引用来重建集合（如 table = new HashSet(table); ）

这类问题很少见。您不会预先为它们设计（哈希函数除外），只有在检测到程序的性能问题时才开始考虑它们。

于 2010-06-17T18:18:03.267 回答
1

除了你想知道的 Hashset 是最快的集合。

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

于 2010-06-17T16:25:25.207 回答
1

散列容器在插入和检索方面接近 O(1)，因此从数量级的角度来看，您不会比这更好。

在散列容器中，随着时间的推移，你的性能将与两件事有关：散列函数提供的分布有多好，以及它的计算速度有多快。这些是不等价的 - 一个分布不佳的函数（最终会出现很多冲突）将比一个更慢但更好的分布式哈希函数对性能影响更大。

因此，如果你能想出一个计算速度也非常快的完美哈希函数，那将是一个改进。以特定方式约束数据可能会使这更容易。但是，你很可能，无论你想出什么都不会像已经存在的那么好。

于 2010-06-17T17:00:27.807 回答