HashSet<int> 和 List<int> 的快速交集

Question

我有一个HashSet<int>和一个List<int>（Hashset 大约有 300 万个项目，List 大约有 300k 个项目）。

我目前使用它们相交

var intersected = hashset.Intersect(list).ToArray();

我想知道是否有更快的方法来做到这一点。也许并行？

Answer 1

HashSet如果两个哈希集之间执行交集，则IntersectWith有一种优化方法。使用方法我们可以相交并使用下一个方法：IntersectWithHashSetList

private static IEnumerable<int> Intersect(HashSet<int> hash, List<int> list)
{
    HashSet<int> intersect = new HashSet<int>(list);
    intersect.IntersectWith(hash);
    return intersect;
}

我测量了（使用Stopwatch）您的原始方法 ( Linq Intersect)、@TheodorZoulias 提出的方法 (HashSet Contains和HashSet Contains Parallel) 以及我的方法 ( HashSet IntersectWith) 的性能。结果如下：

------------------------------------------------------------------------
|         Method            | Min, ms | Max, ms | Avg, ms | StdDev, ms |
------------------------------------------------------------------------
| Linq Intersect            |   135   |   274   |   150   |     17     |
| HashSet Contains          |    25   |    44   |    26   |      2     |
| HashSet Contains Parallel |    12   |    53   |    13   |      3     |
| HashSet IntersectWith     |    57   |    89   |    61   |      4     |
------------------------------------------------------------------------

从表中我们可以看出，最快的方法是HashSet Contains Parallel，最慢的方法是Linq Intersect。

这是用于衡量性能的完整源代码。