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

Question

假设我有一个类:

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

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

在这种情况下，什么更好？

a) 以uniqueField为键的字典

Dictionary<int, C> d;

或 b) 列表？

List<C> l;

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

一)

d[searchedUniqueField]

二)

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

Answer 1

假设您有相当多的实例，那么在字典中查找项目的速度可能多。基本上是一个 Dictionary<,>是 hash table , 除了碰撞之外，查找时间复杂度为 O(1)。

现在，如果集合真的很小，那么查找哈希码、计算正确的桶、然后在该桶中查找匹配的哈希码、然后执行键相等性检查的额外开销可能比仅检查每个元素花费更长的时间在列表中。

如果您可能有很多实例但可能没有，我通常会选择字典方法。一方面，它表达了您实际想要实现的目标:一种通过键访问元素的简单方法。小型集合的开销不太可能很大，除非您的小型集合比大型集合多得多。