.net 大数据量，查找Where优化（List的Contains与Dictionary的ContainsKey的比较）

 最近优化一个where查询条件，查询时间很慢，改为用Dictionary就很快了。

 一、样例

假设：listPicsTemp 有100w条数据，pictures有1000w条数据。

使用第1段代码执行超过2分钟。

var listPicsTemp = new List<string>();

pictures = pictures.AsParallel().Where(d => listPicsTemp.Contains(d.Pic)).ToList();

使用第2段代码执行十几毫秒。

var listPicsTemp = new List<string>();

var dicPicsTemp = listPicsTemp.Where(d => d != null).Distinct().ToDictionary(d => d);//使用Dictionary类型，速度快很多

pictures = pictures.AsParallel().Where(d => dicPicsTemp.ContainsKey(d.Pic)).ToList();

二、为什么Dictionary这么快呢？查看了一下微软官方文档。

下面截图来源：https://docs.microsoft.com/zh-cn/dotnet/api/system.collections.generic.dictionary-2?view=netframework-4.7.2

三、查看源码

List的源码：https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

List的Contains，是循环for查找的。

Dictionary的源码： https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,bcd13bb775d408f1

Dictionary的ContainsKey，是通过hash查找的。

 

 四、小结：

1、Dictionary<TKey,TValue>类实现为哈希表。ContainsKey() 内部是通过Hash查找实现的，查询的时间复杂度是O(1)。所以，查询很快。（List的Contains是通过for查找的）

2、Dictionary不是线程安全的。（查看微软官方文档，确实能学到很多知识盲区。）