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

假设我有一堂课：

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);

最佳答案

假设您有很多实例，那么在字典中查找项目可能会更快。基本上，Dictionary<,>是hash table，其O（1）查找不是由于冲突引起的。

现在，如果集合真的很小，那么查找哈希码，计算正确的存储区，然后在该存储区中查找匹配的哈希码，然后执行键相等性检查所花的时间可能比仅检查列表中的每个元素还要长。 。

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

关于c# - 在列表和字典中搜索的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31609289/