内存中双集合关联查询性能过慢，求优化方案

内存中有firstList和secondList两个对象集合，需求是找出firstList中所有Id与secondList项的RelatedId匹配的元素，当前实现代码如下：

var items = firstList.Where(item => secondList.Any(secondItem => item.Id == secondItem.RelatedId));

当两个集合规模稍大时，这段查询耗时极长，请问如何通过拆分或重构查询来提升效率？

优化方案 #

原代码的问题在于嵌套遍历，时间复杂度为O(n*m)（n是firstList的元素数量，m是secondList的元素数量），数据量越大，性能下降越明显。可以通过以下方式优化：

• 先将secondList中的RelatedId提取到**哈希集合（HashSet）**中，HashSet的查找操作时间复杂度为O(1)，能大幅降低整体计算成本。

重构后的代码如下：

// 提取所有需要匹配的RelatedId到HashSet，仅需遍历secondList一次
var relatedIds = new HashSet<int>(secondList.Select(s => s.RelatedId));
// 遍历firstList，用HashSet快速判断是否匹配
var items = firstList.Where(item => relatedIds.Contains(item.Id));

补充说明 #

如果RelatedId不是int类型（比如Guid、string），只要该类型支持哈希计算，同样可以用HashSet来实现优化。这种方式的整体时间复杂度为O(n+m)，相比原方案性能提升非常显著，尤其是在集合元素数量较多的场景下。

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