如何高效合并对象数组：按标识符去重并按排序值排序？

嘿，这个场景我太熟悉了——长列表下先暴力去重再排序确实会拖慢性能，咱们换个思路用**哈希表（Map）**来处理，能把整体时间复杂度从O(n*m + (n+m)log(n+m))降到O(n+m + (n+m)log(n+m))，合并阶段的效率提升特别明显。

具体实现步骤（以JavaScript为例，其他语言思路一致） #

1. 用哈希表存储现有数组元素
   把现有数组arrayA的元素存入Map，以identifier作为Key，这样后续查找、更新元素的时间复杂度都是O(1)：

   const itemMap = new Map();
   // 加载现有数组到Map
   arrayA.forEach(item => {
     itemMap.set(item.identifier, item);
   });
   

2. 合并接口返回的新数组
   遍历接口返回的arrayB，直接用新元素覆盖Map中相同identifier的旧元素，不存在的就直接添加：

   // 合并新数组，新元素覆盖旧元素
   arrayB.forEach(item => {
     itemMap.set(item.identifier, item);
   });
   

3. 将Map值转数组并排序
   把Map中的所有值提取成数组，再按sortValue排序：

   // 转数组并按排序值升序排列
   const mergedSortedArray = Array.from(itemMap.values()).sort((a, b) => a.sortValue - b.sortValue);
   

用你的示例验证 #

• 初始arrayA：[{identifier: 'A', sortValue:1}, {identifier: 'B', sortValue:4}, {identifier: 'C', sortValue:6}]
• 接口返回arrayB：[{identifier: 'D', sortValue:2}, {identifier: 'A', sortValue:3}, {identifier: 'C', sortValue:5}, {identifier: 'G', sortValue:7}]
• 经过Map处理后，Map中的元素为：A:3, B:4, C:5, D:2, G:7
• 排序后结果：[{identifier: 'D', sortValue:2}, {identifier: 'A', sortValue:3}, {identifier: 'B', sortValue:4}, {identifier: 'C', sortValue:5}, {identifier: 'G', sortValue:7}]，完全符合预期。

为什么这是最优方案？ #

• 合并阶段：原来的暴力去重（比如双重循环找重复）时间复杂度是O(n*m)，用Map后变成O(n+m)，数据量越大，性能差距越明显。
• 排序阶段：排序的时间复杂度O(k log k)（k是合并后数组长度）是排序算法的理论下限，没法再优化，所以我们能做的就是把前面的合并步骤做到最优。

如果你的业务场景中排序值是持续递增的，还可以考虑维护一个有序的数据结构（比如二叉搜索树），但实现复杂度会高很多，对于大多数场景来说，用Map合并后排序已经是性价比最高的方案了。

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