如何快速查找存在于列表B但不存在于列表A的人员（C# LINQ场景）

性能慢的根因 #

你当前的写法时间复杂度是O(n*m)，n是listofPersons的长度，m是allUsedPersons的长度：每遍历1个listofPersons里的人员，都要完整遍历一遍allUsedPersons的所有元素判断Id是否匹配，当两个列表数据量稍大时，耗时会呈指数级增长。

优化方案 #

方案1：用HashSet存已使用人员Id（最通用、改造成本最低） #

利用HashSet的O(1)查找特性，把整体时间复杂度降到O(n+m)，数据量越大性能提升越明显，代码示例：

// 先把所有已使用人员的Id存入HashSet，仅需遍历一次allUsedPersons
var usedIdSet = new HashSet<int>(allUsedPersons.Select(p => p.Id));
// 遍历listofPersons时直接查HashSet，每次查找都是O(1)
var missingPeople = listofPersons.Where(p => !usedIdSet.Contains(p.Id)).ToList();

方案2：用LINQ的Except方法（代码更简洁，适合复用场景） #

如果需要多处用到按Id判断人员相等的逻辑，可以自定义比较器，调用原生Except方法，内部实现也是基于HashSet，性能和方案1一致：
首先自定义Id比较器：

public class PersonIdEqualityComparer : IEqualityComparer<Person>
{
    public bool Equals(Person x, Person y) => x?.Id == y?.Id;
    public int GetHashCode(Person obj) => obj?.Id.GetHashCode() ?? 0;
}

调用代码：

var missingPeople = listofPersons.Except(allUsedPersons, new PersonIdEqualityComparer()).ToList();

特殊场景补充 #

如果两个列表是直接从数据库查询出来的，不要先把全量数据拉到内存再过滤，直接在EF/EF Core查询阶段做过滤，生成NOT EXISTS的SQL在数据库层面执行，性能会更高：

var missingPeople = await dbContext.ListOfPersons
    .Where(p => !dbContext.AllUsedPersons.Any(a => a.Id == p.Id))
    .ToListAsync();

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