交集、并集、差集是集合操作中经常遇见的需求，本文分享一种基于hash的标记算法来实现高性能的合集操作
本文以交集(intersect)实现为例，实现一个可运行算法demo。

传统思维

当遇见2-n个集合需要进行交集操作时，线性思维会让我想到循环比较。比如三个集合相交

[1,2,3,4] ∩ [1,2,3,4] ∩ [1,2,3,4]

为了求出结果，我会

for(集合1){
  for(集合2 ，集合3，...){
    对比相同
  }
}

经过20次循环后，终于算出交集是[1,2,3,4]

2(匹配1) + 4(匹配2) + 6(匹配3) + 8(匹配4)

循环算法简单易实现，直到集合数量级达到下面的程度

200个集合，每个集合2000个数字

之所以没有使用更大的集合来测试是因为，再多2个0你就得盯着控制台看一天 。囧rz

可以看到在200*2000数量级下求交集一共

• 循环了398,199,000次
• 消耗了1250ms（不考虑多次执行优化）

∑M*n => 199(2000+1)1000

当然，在某些场景下可以进行优化（见本文末尾内容），但算法结构决定了这个结果。

标靶算法

先来看看Hash算法结果，加大测试量

新算法结果

可以看到在200*200000数量级下求交集一共

• 循环了40,000,000次
• 消耗了1192ms（不考虑多次执行优化）

M*N

从循环次数可以看出来，标记算法在 全交集 场景时最多 【每个元素遍历一次 】，而这就是标记算法的核心 —— 降维处理。

算法描述

要进行降维处理，首先要确定交集标靶(见本文算法优化章节第一条)映射Map，然后就可以顺序循环所有元素（而非集合）一次，发现相同标靶时把映射Map中对应标靶的计数+1（同一个集合内相同标靶不要加），完成所有元素遍历后核对映射Map中标靶计数与集合数量相同的则为相交元素。

代码在此不进行展示，需要查看可以直接查看 func.js源码

效果对比

与同类库Lodash对比，如下

Lodash Func.js

算法优化

在实际业务中求交集时会有多种场景，比如集合内元素数量不定、类型不定等。通常可以分为两类：

• 全交集 - 就像本文图中所讲示例，所有集合中的所有元素全部相同。这种场景下优化手段有限
• 部分交集 - 一种是集合长度相同，但是元素内容不同的场景；还有集合长度不同，元素内容也不同的场景；
  针对

对于部分交集场景可以有如下优化手段

1. 按集合长度排序并以最短集合内容为交集标靶，比如

   [1,2] ∩ [1,3,4] ∩ [1,2,3,4]
   

   就可以提前确定最多可相交元素只有[1,2]。
2. 以标靶检索后续每个集合时，如果已经中靶 —— 比如 [1,2,3,4] 集合中1，2已经被找到时就可以中断后续检索了
3. 如果标靶在第二个集合中不存在，那么也没必要继续检索后续集合 —— 比如2在 [1,3,4] 中不存在就已经确定无法相交，可以中断