使用Dictionary <Foo,Foo>而不是List <Foo>来加速调用包含()

Question

我对C#中的泛型集合有疑问.如果我需要存储一组项目,并且我经常需要检查项目是否在集合中,那么使用Dictionary而不是List会更快吗？

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

感谢您抽时间阅读.

Answer 1

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

值得注意的是,它Dictionary是在C#2.0 HashSet中添加的,并且是在3.5中添加的,所以对于所有那段时间而言,当你想要一个Set时,使用一个字典实际上是相当普遍的,因为那是你所拥有的(没有自己动手) .当我被迫这样做时,我只是在值中加入null,而不是将项目作为键和值,但这个想法是一样的.

Answer 2

只要使用HashSet<Foo>,如果你只关心是快速遏制测试.

A Dictionary<TKey, TValue>用于根据键查找值.

A List<T>用于随机访问和动态增长属性.

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

您没有根据密钥查找值.您不担心随机访问,而是快速控制检查.这里正确的概念是HashSet<T>.

Answer 3

假设列表中只有一个项目的副本,那么ISet<T>具体就是适当的数据结构HashSet<T>.

也就是说,我已经看到时间表明Dictionary<TKey, TValue> ContainsKey呼叫速度比偶数快一点HashSet<T>.无论哪种方式,它们都将比普通List<T>查找更快地加载.

请记住,这两种方法(HashSet和Dictionary)都依赖于相当好的实现Equals 和 GetHashcode实现T. List<T>只依靠Equals