14

我需要检查特定字符串是否包含在其他字符串中：

private bool Contains(string field)
{
   return this.Fields.Contains(field); // HashSet<string> local property
}

如果只有一项任务，最好使用哪种容器类型 - 保存多个字符串并检查另一个字符串是否进入？

4

2 回答 2

39

哈希集有效吗？当然。但这不是你问的问题。您要求尽可能快的查找。

它是最快的吗？不，当然不是，无论如何都不是。

首先，为了谈论“最快”，我们需要准确描述“最快”的含义。你的意思是：

  • 最小的最坏情况时序
  • 多次计时平均的最小平均计时
  • 给定特定使用模式的最小平均时间
  • 别的东西

? 请准确说明“尽可能快”的含义。我们可以为您设计一个理论上最快的算法，前提是我们准确地知道最快对您意味着什么。

例如，假设您正在编写一个编译器。在编译器中我们必须一直做的事情是检查特定字符串是否在字符串列表中。也许我们正在检查字符串是否是关键字，因此我们必须查找给定字符串是否在集合内 {"int", "double", "for", "foreach", "class" ... }

我们可以将它们放入哈希集中并获得不错的性能。但如果我们想要最好的性能，我们可以做得更好。例如，我们可以对数十亿行现有源代码进行分析，找出哪些关键字最常见，哪些最不常见，然后编写一个自定义哈希表，针对 (1) 快速拒绝根本不是关键字，以及（2）以识别其他关键字为代价快速识别最常见的关键字。

请注意，这需要静态分析；尽管它在典型情况下表现良好，但在使用大量稀有关键字的罕见情况下表现不佳。我们可以采取的另一种方法是编写一个自调整哈希表，该哈希表可以动态识别何时频繁搜索特定字符串。

例如，假设您正在编写 JScript 运行时的实现。我们经常必须在一组字符串中寻找一个字符串：

for(i = 0; i < 10; ++i) { foo.bar(i); }

在这里，我们必须在由“foo”标识的对象中查找字符串“bar”十次。“foo”中实现该查找的哈希表在第一次循环中注意到“bar”已被使用，因此它动态调整哈希表结构，以便第二次通过循环，查找更快。这是我们在实现 JScript 时采用的策略。

现在，这优化了循环的情况，但它使这种情况可能比它可能的慢： 

for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); }

因为我们没有做更多的分析并意识到“嘿，我们只是重新优化了这个哈希表 3 次，现在我们要重新做一遍，也许我们应该保持原样。”

对我们来说幸运的是，我们并没有像您一样寻求最快的查找。我们只是在寻找一个相当快速的查找。

您能否仔细而完整地描述您的用例究竟是什么，以实现最快的查找？您可以使用许多算法来加快查找速度，但它们变得非常复杂。

于 2010-02-14T18:04:19.267 回答
14

是的，HashSet 非常适合这一点，因为它包含一个要查找的值，而 Dictionary 需要一个键和一个值。

于 2010-02-13T20:50:51.103 回答