c# - 使用字典而不是列表加快对 Contains() 的调用

Question

我对 C# 中的泛型集合有疑问。如果我需要存储一个项目的集合，并且我经常需要检查一个项目是否在集合中，使用字典而不是列表会更快吗？

我听说检查一个项目是否在集合中相对于列表的大小是线性的，相对于字典的大小是恒定的。使用 Dictionary 然后将每个键值对的 Key 和 Value 设置为同一个对象，这是其他程序员在这种情况下经常做的事情吗？

感谢您抽时间阅读。

Answer 1

HashSet<Foo>如果您关心的是快速遏制测试，请使用。

ADictionary<TKey, TValue>用于根据键查找值。

AList<T>用于随机访问和动态增长属性。

AHashSet<T>用于对集合进行建模并提供快速遏制测试。

您不是在查找基于键的值。您不必担心随机访问，而是担心快速收容检查。这里正确的概念是HashSet<T>.

Answer 2

假设列表中只有一个项目的副本，那么适当的数据结构是ISet<T>，特别是HashSet<T>。

也就是说，我已经看到时间表明Dictionary<TKey, TValue> ContainsKeycall 比 even 快一点HashSet<T>。无论哪种方式，它们都将比普通List<T>查找更快地加载。

请记住，这两种方法（HashSet 和 Dictionary）都Equals 依赖 GetHashcode于T. List<T>只依赖Equals

Answer 3

是的，是的。也就是说，您可能想要使用HashSet，因为您不需要键和值，您只需要一组项目。

还值得注意的是，它Dictionary是在 C# 2.0 中添加的，并且HashSet是在 3.5 中添加的，因此在这之间的所有时间里，当你想要一个 Set 时使用 Dictionary 实际上是相当普遍的，因为这就是你所拥有的（而不是你自己的） . 当我被迫这样做时，我只是将 null 放在值中，而不是将项目作为键和值，但想法是一样的。

Answer 4

Dictionary 或 HashSet 将使用更多内存，但提供（几乎）O(1) 寻道时间。

Answer 5

您可能想查看HashSet，它是唯一对象的集合（只要该对象实现 IEquality 比较器）。

Answer 6

您提到 using List<T>，这意味着排序可能很重要。如果是这种情况，那么您可能还想查看SortedSet<T>类型。