优化含对象的两个大数组交集计算的性能方案咨询

原代码用filter嵌套some的方式计算交集，本质是两层遍历，时间复杂度为O(n*m)——当两个数组都是超大级别的时候，这种嵌套遍历会导致运行耗时急剧上升，这就是性能瓶颈所在。

优化思路 #

把其中一个数组的匹配标识（这里是firstName+lastName的组合）提前存入哈希集合（Set），将原本O(m)的查找操作降到O(1)，整体时间复杂度优化为O(n + m)，大幅提升处理超大数组的效率。

优化后的代码 #

const arr1 = [  
    {  
       "number":"123",
       "firstName":"John",
       "lastName":"Smith",
       "email":"test1@test.com",
    },
    {  
       "number":"1234",
       "firstName":"Chad",
       "lastName":"Baker",
       "email":"test2@test.com",
    }
];
 
const arr2 = [  
    {  
        "number":"12345",
        "firstName":"Chad",
        "lastName":"Baker",
        "email":"test2@test.com",
    },
    {  
        "number":"123456",
        "firstName":"John",
        "lastName":"Smith",
        "email":"test1@test.com",
    }
];

// 先将arr2的姓名组合存入Set，一次遍历完成
const nameSet = new Set(arr2.map(item => `${item.firstName}-${item.lastName}`));

// 遍历arr1，用Set快速判断是否存在匹配项
const arr3 = arr1.filter(item => {
  const key = `${item.firstName}-${item.lastName}`;
  return nameSet.has(key);
});

console.log(arr3);

补充说明 #

• 如果担心姓名中包含-导致键冲突，可以换用不会出现在字段中的特殊分隔符，比如${item.firstName}||${item.lastName}或者空字符\u0000
• 要是需要基于多个字段匹配，只需要把所有参与匹配的字段组合成唯一键存入Set即可，逻辑完全一致

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