HashSet <T>是最容易查找的容器吗？

Question

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

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

如果只有一个任务,它可以使用的最佳容器类型是什么 - 容纳一些字符串并检查是否有另一个容器进入或不存在？

Answer 1

HashSet有效吗？当然.但那不是你问的问题.您要求尽可能快的查找.

它是最快的吗？不,当然不是,不是任何措施.

首先,为了谈论"最快",我们需要准确描述"最快"的含义.你的意思是:

• 最小的最坏情况时机
• 在许多时间平均的最小平均时间
• 给定特定使用模式的最小平均时间
• 别的

？请准确说明"最快可能"的含义.我们可以为您设计一种算法,理论上只有在我们确切地了解您可能的最快方式时才是最快的算法.

例如,假设您正在编写编译器.我们必须在编译器中一直做的事情是检查特定字符串是否在字符串列表中.也许我们正在检查字符串是否是关键字,所以我们必须查看给定的字符串是否在集合{"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); }

因为我们没有做更多的分析并意识到"嘿,我们只是重新优化了这个哈希表三次,现在我们将再次完成这一切,也许我们应该保持原样."

对我们来说幸运的是,我们并不像您一样,寻找最快的查找.我们只是在寻找一个合理快速的查找.

您能否仔细并完整地描述您的使用案例究竟是什么,以便尽可能快地查找？您可以使用许多算法来加速查找,但它们变得非常复杂.

Answer 2

是的,HashSet是完美的,因为它包含一个要查找的值,而不像需要键和值的Dictionary.