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中的几个项目。

利用良好的散列算法，Dictionary搜索可以接近O（1），这意味着搜索时间与字典的大小无关。另一方面，列表是O（n），意味着时间（平均）与列表大小成正比。

如果只是有关键项目（不映射键的值）您也可以尝试一个HashSet。它具有O（1）查找的优点，而不需要字典的Value一侧的开销。

（授予的开销可能是最小的，但为什么拥有它，如果你不需要它？），因为它需要的时间保持不变

Answer 2

对于查找字典通常是最好的。随着清单的增加，清单越大。

参见：http://www.dotnetperls.com/dictionary-time

Answer 3

我建议使用Dictionary时查找的数量大大超过插入的数目。当您总是少于四件物品时，使用List就可以了。

对于查找，Dictionary通常是更好的选择。所需的时间是平坦的，O（1）恒定的时间复杂度。该列表具有O（N）线性时间复杂度。三个元素的循环速度比在Dictionary中查找得快。