如何在JS/TS、ES6(7)中无嵌套循环实现数组关联映射

原始数组 #

const history = [
   { type: 'change', old: 1, new: 2 },
   { type: 'change', old: 3, new: 4 },
];

const contents = [
   { id: 1, info: 'infor1' },
   { id: 2, info: 'infor2' },
   { id: 3, info: 'infor3' },
   { id: 4, info: 'infor4' },
];

期望目标数组 #

const detailHistory = [
   { type: 'change', old: { id: 1, info: 'infor1' }, new: { id: 2, info: 'infor2' } },
   { type: 'change', old: { id: 3, info: 'infor3' }, new: { id: 4, info: 'infor4' } },
];

解决方案 #

核心思路是先把contents数组转换成以id为键的映射对象，这样后续查找对应元素的时间复杂度为O(1)，再通过一次遍历完成history数组的转换，全程仅需两次线性循环，完全避免嵌套循环。

实现代码

// 1. 构建内容映射表：将contents的id作为键，对应对象作为值
const contentMap = contents.reduce((acc, curr) => {
  acc[curr.id] = curr;
  return acc;
}, {});

// 2. 遍历history数组，替换old和new字段为映射表中对应的对象
const detailHistory = history.map(entry => ({
  ...entry, // 保留原有的type字段
  old: contentMap[entry.old],
  new: contentMap[entry.new]
}));

完整验证代码

const history = [
   { type: 'change', old: 1, new: 2 },
   { type: 'change', old: 3, new: 4 },
];

const contents = [
   { id: 1, info: 'infor1' },
   { id: 2, info: 'infor2' },
   { id: 3, info: 'infor3' },
   { id: 4, info: 'infor4' },
];

const contentMap = contents.reduce((acc, curr) => {
  acc[curr.id] = curr;
  return acc;
}, {});

const detailHistory = history.map(entry => ({
  ...entry,
  old: contentMap[entry.old],
  new: contentMap[entry.new]
}));

console.log(detailHistory);
// 输出结果与期望的detailHistory完全一致

这种实现的时间复杂度为O(n + m)（n为contents数组长度，m为history数组长度），比嵌套循环的O(n*m)效率更高，同时代码简洁易读。

内容的提问来源于stack exchange，提问作者Tran Quang Hung