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字典侧面的开销.

(承认开销可能很小,但如果你不需要它,为什么要这样做呢？)

Answer 2

对于查找，字典通常是最好的，因为它花费的时间保持不变。对于列表，它会随着列表变得越大而增加。