C# - 搜索字典的键与搜索列表中的值

Question

就搜索速度而言，搜索字典的键或列表的值哪个更好？

换句话说，哪一个最可取？

Dictionary<tring,string> dic = new Dictionary<string,string>();
if(dic.ContainsKey("needle")){ ... }

或者

List<string> list = new List<string>();
if(list.Contains("needle")){ ... }

Answer 1

如果“更好”是指“更快”，那么请使用字典。字典键按散列码组织，因此查找速度明显快于列表搜索，而不仅仅是 ocllection 中的几个项目。

使用良好的哈希算法，字典搜索可以接近 O(1)，这意味着搜索时间与字典的大小无关。另一方面，列表的复杂度为 O(n)，这意味着时间(平均而言)与列表的大小成正比。

如果您只是有键项(没有将键映射到值)，您也可以尝试 HashSet .它具有 O(1) 查找的优点，而没有字典的 Value 端的开销。

(假设开销可能很小，但如果您不需要它，为什么还要它呢？)