C#中List<T>.Contains()方法为何执行速度过慢？

需要从全量车辆列表中，移除ID存在于指定待删除ID集合中的对象，相关变量定义如下：

List<Vehicle> vehicles;  // 全量车辆列表，共260条数据
List<int> vehiclesIds;  // 需要从原列表移除的ID集合，长度小于260

两种实现方式性能差异极大：

• 写法1：直接在RemoveAll中调用待删除列表的Contains方法，总耗时25~30秒

vehicles.RemoveAll(e => vehiclesIds.Contains(e.Id));

• 写法2：循环遍历待删除ID，逐个调用RemoveAll移除对应车辆，总耗时仅8~20毫秒

foreach (var vehiclesId in vehiclesIds)
{
    vehicles.RemoveAll(e=> vehiclesId == e.Id);
}

经StopWatch多次测试确认，性能瓶颈来自List.Contains()调用。

260条量级的内存数据做匹配，无论如何不可能出现秒级耗时，实际测试得到的巨大性能差核心原因是：vehiclesIds不是已经加载完成的内存List集合，而是延迟执行的IEnumerable序列（比如未调用ToList()/ToArray()的数据库查询、LINQ延迟查询结果）。
两种写法的执行逻辑差异：

• 写法1中，RemoveAll每遍历一条Vehicle记录，就会调用一次vehiclesIds.Contains(e.Id)，每一次Contains调用都会重新从头枚举整个vehiclesIds序列。如果vehiclesIds是数据库查询，等于每判断一条数据就发起一次数据库请求，260条数据就要发260次请求，耗时自然会飙升到几十秒。
• 写法2中，foreach循环会在最开始就完整枚举一次vehiclesIds序列，把每个ID以值类型int的形式存为局部变量，后续RemoveAll的匹配判断只是直接和内存里的int值做相等比较，不会重复触发vehiclesIds的枚举，因此速度极快。

补充：如果两个列表都是已经加载完成的内存集合，第一种写法的时间复杂度是O(车辆数 * 待删除ID数)，第二种是O(待删除ID数 * 车辆数)，理论复杂度完全一致，不可能出现数量级的性能差。

不管待删除ID集合是内存集合还是延迟查询序列，最高效稳定的写法是先将待删除ID转为HashSet：

// 仅枚举一次待删除ID序列，转为查询复杂度O(1)的HashSet
var toRemoveIds = new HashSet<int>(vehiclesIds);
// 单次遍历全量车辆列表即可完成过滤，总复杂度O(车辆数)
vehicles.RemoveAll(e => toRemoveIds.Contains(e.Id));

这个写法的优势：

• 只会触发一次待删除ID序列的枚举，完全避免延迟查询重复执行的问题
• 不需要多次遍历原车辆列表，执行效率比嵌套循环的写法更高
• 后续数据量上涨到十万、百万级时，性能也不会出现明显衰减

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