如何高效地将新消息合并到状态数组中（避免重复 ID）-js教程-PHP中文网

如何高效地将新消息合并到状态数组中（避免重复 ID）

本文介绍一种时间复杂度为 O(n + m) 的高效方案：利用 Set 预存已有 ID，再通过 filter 筛选待插入消息，显著优于 forEach 或 reduce 中嵌套 find 的 O(n×m) 方案。

本文介绍一种时间复杂度为 o(n + m) 的高效方案：利用 `set` 预存已有 id，再通过 `filter` 筛选待插入消息，显著优于 `foreach` 或 `reduce` 中嵌套 `find` 的 o(n×m) 方案。

在前端状态管理（如 Redux、React state）或实时消息处理场景中，常需将一批新消息合并进现有数组，且要求按 ID 去重、保留原数组顺序、新消息前置。原始实现中使用 forEach 或 reduce 配合 Array.prototype.find() 判断存在性，看似直观，但隐藏严重性能问题。

⚠️ 性能陷阱：嵌套遍历的代价

原始 forEach 版本：

messages.forEach((message) => {
  const alreadyInState = state.find(msg => msg.id === message.id); // ❌ 每次 O(n)
  if (!alreadyInState) messagesToMerge.push(message);
});

对每条新消息，都需遍历整个 state 数组查找匹配项。若 state 含 10,000 条，messages 含 500 条，则最坏执行约 500 × 10,000 = 5,000,000 次比较 —— 时间复杂度为 O(n × m)。

Cursor

一个新的IDE，使用AI来帮助您重构、理解、调试和编写代码。

下载

reduce 版本问题更甚：不仅同样嵌套 find，还错误地将 state 作为初始值传入 acc，导致后续 acc.find() 在不断增长的累积数组上重复搜索，逻辑混乱且无法正确去重（实际会漏判或重复插入）。

✅ 最优解：用 Set 实现 O(1) 查找

核心思路：空间换时间。先将 state 中所有 id 提取为 Set，其 has() 方法平均时间复杂度为 O(1)，整体降至线性：

function getNewState(state, messages) {
  // Step 1: 构建 ID 集合 —— O(n)
  const idsInState = new Set(state.map(msg => msg.id));

  // Step 2: 过滤出不存在于 state 的新消息 —— O(m)
  const messagesNotInState = messages.filter(msg => !idsInState.has(msg.id));

  // Step 3: 合并（新消息在前）—— O(m + n)
  return [...messagesNotInState, ...state];
}

✅ 时间复杂度：O(n + m)
✅ 空间复杂度：O(n)（仅额外存储 ID）
✅ 语义清晰、无副作用、函数式友好

? 验证示例

const state = [
  { id: 1, text: 'text 1' },
  { id: 2, text: 'text 2' },
  { id: 3, text: 'text 3' }
];

const newState = getNewState(state, [
  { id: 1, text: 'text 1 (dup)' }, // 被过滤
  { id: 4, text: 'text 4' }       // 新增
]);

console.log(newState);
// → [
//      { id: 4, text: 'text 4' },
//      { id: 1, text: 'text 1' },
//      { id: 2, text: 'text 2' },
//      { id: 3, text: 'text 3' }
//    ]