C#中查找列表匹配项时创建HashSet是否比直接遍历列表更快？

当前小规模场景的性能表现 #

当两个列表长度都很小（比如你提到的ListA固定3个元素，ListB最多数十个元素）时，双层嵌套遍历的执行速度更快。
核心原因很直接：

• 你当前场景下双层循环的总比对次数最多也就3*数十 = 100~200次，C#中字符串的==判断首先会做快速引用相等检查，引用不一致时才会逐字符比对内容，这个量级的操作CPU只需要几十纳秒就能完成。
• 你担心的HashSet初始化开销确实存在：哪怕你用listB.Length预设了初始容量，省去了后续扩容的内存拷贝成本，依然省不掉HashSet实例本身的堆内存分配、每个入集元素的哈希值计算、内部存储桶结构初始化的固定开销，这些开销在百次比对的量级下，比直接双层循环的成本高2~5倍，反而会带来负面性能影响。

规模扩容后的性能拐点 #

HashSet方案的性能优势会随着列表长度增长快速显现，拐点大概出现在两个列表长度的乘积（即双层循环总比对次数）超过200~300次的时候：

• 双层嵌套遍历的时间复杂度是O(n*m)，耗时会随两个列表长度增长呈平方级上升，等两个列表都扩容到上百元素时，总比对次数会破万，性能下降会非常明显。
• HashSet方案的时间复杂度是O(n+m)，构建集合和遍历查找的耗时都是随列表长度线性增长的，当列表规模到上百、上千量级时，HashSet的执行速度会比双层循环快几个数量级，初始化的固定开销完全可以被摊薄到可以忽略的程度。

面向后续扩展的优化建议 #

考虑到你后续调用频率会提升到每秒数千次、且列表存在明确扩容预期，不建议非此即彼选某一种固定方案，可以做两个简单优化覆盖全场景：

• 优先做可复用缓存：如果传入的ListB不是每次调用都会全量变更，不要每次检测都新建HashSet，只在ListB内容发生修改时重新构建一次HashSet缓存，后续检测直接用缓存好的集合做Contains判断，这样既消除了每次初始化HashSet的开销，又能拿到O(1)复杂度的查找性能，大小数据量场景都能跑满速度。
• 如果每次传入的列表都是全新内容、无法做缓存，可以加一个极简单的阈值判断：当两个列表长度乘积小于200时走双层循环逻辑，大于阈值时再临时构建HashSet做查找，兼顾小数据量的低开销和大数据量的扩展性。

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