在列表和字典中搜索的复杂性

Question

假设我有一节课:

class C
{
    public int uniqueField;
    public int otherField;
}

这是实际问题的非常简化的版本.我想存储此类的多个实例,其中"uniqueField"对于每个实例应该是唯一的.

在这种情况下更好的是什么？

a)以uniqueField为关键字的字典

Dictionary<int, C> d;

或b)清单？

List<C> l;

在第一种情况(a)中,相同的数据将被存储两次(作为键和作为类实例的字段).但问题是:在字典中查找元素比在列表中更快吗？还是同样快？

一个)

d[searchedUniqueField]

b)

l.Find(x=>x.uniqueField==searchedUniqueField);

Answer 1

假设你有很多实例,在字典中查找项目可能要快得多.基本上a Dictionary<,>是一个哈希表,除了由于冲突之外还有O(1)查找.

现在,如果集合非常小,那么查找哈希码,计算正确的存储桶然后查看该存储桶以匹配哈希码,然后执行密钥相等性检查的额外开销可能比检查列表中的每个元素花费更长的时间.

如果您可能有很多实例但可能没有,我通常会选择字典方法.首先,它表达了您实际想要实现的目标:通过密钥访问元素的简单方法.小集合的开销不太可能非常显着,除非您拥有的集合远小于大集合.