我读了很多关于 HashSet 和 LINQ 集操作的文章和博客，我的印象是 linq 交集方法在内部使用散列集作为第一个集，IEnumerable 作为第二个集。因此，两者之间的差异是 O（n + m） 表示 linq 交集，而 O（n） 表示两个散列集之间的散列集交集。我可以得到确认吗？MSDN 中未记录 LINQ 交叉的大 O。
嗯
，它是特定于实现的，所以理论上它可能会改变 - 但基本上区别在于使用HashSet.IntersectWith你从一个哈希集开始，所以你只需要迭代一个集合。
"明显"的实现将分别为Intersect和IntersectWith提供O（M + N）和O（N）复杂性 - 当然，假设有一个不错的哈希代码。看到任何其他实现，我会感到非常惊讶，我当然没有看到任何证据表明任何版本的 .NET 都附带了除此之外的任何内容。
可以说，如果Intersect的两个参数都已经HashSet<T>则可以对其进行优化，以仅迭代较小的集合并检查每个元素是否在较大的集合中。但是，这还有另一个问题，即集合可能不使用相同的比较器作为彼此或作为Intersect调用。
请参阅我的 Edulinq 实现并发布更多详细信息，包括有关 MSDN 中不准确的注释。MSDN 声称（在撰写本文时）：
枚举此方法返回的对象时，Intersect 首先枚举，收集该序列的所有不同元素。然后，它枚举第二个，标记在两个序列中出现的元素。最后，标记的元素按收集顺序生成。
这实际上不是真的，无论是在顺序还是时间方面：
- 它是最初枚举的
second（完全，当MoveNext()首次在返回的序列上调用时） - 结果是在迭代
first时生成的 - 它们是流式传输的，而不是 MSDN 声明的"标记所有内容然后生成结果"