Dictionary.TryGetValue与List.Any哪个效率更高？

我遇到这样一个场景：需要在循环里判断元素是否属于某个集合。直接的做法是调用List的Any方法，示例代码如下：

public class Person
{
    public int Id { get; set;}
    public string Name { get; set;}
}

List<Person> persons = new List<Person>();

foreach(int personId in personIds)
{
    if(persons.Any(x => x.Id == personId))
    {
       // do something
    }
}

另一种开发者常用的方式是使用Dictionary的TryGetValue方法，示例代码如下：

Dictionary<int, Person> personLookup = new Dictionary<int, Person>();
foreach(int personId in personIds)
{
   if(personLookup.TryGetValue(personId, out var person))
   {
      // do something
   }
}

请问这两种方式哪种效率更高？

毫无疑问，使用Dictionary.TryGetValue的效率要远高于List.Any，核心差异在于两者的查找时间复杂度：

• List的Any方法本质是线性遍历列表，最坏情况下要遍历所有元素才能得到结果，时间复杂度为O(n)。如果外层还有遍历personIds的循环，整体时间复杂度会变为O(m*n)（m为personIds的长度，n为persons列表的长度），数据量越大，性能下降越明显。
• Dictionary基于哈希表实现，TryGetValue的查找操作平均时间复杂度为O(1)，加上外层循环后整体时间复杂度仅为O(m)，在数据量较大时性能优势极其显著。

需要补充的是：使用Dictionary前需要先将List转换为以Id为键的Dictionary<int, Person>，这一步的时间复杂度是O(n)，但这是一次性开销，后续的多次查找会快速摊平这个成本。如果只是单次查找，两者性能差异不大，但循环内的多次查找场景下，Dictionary的优势会非常突出。

内容的提问来源于stack exchange，提问作者Pawan Nogariya