请验证：用HashMap替代双重遍历匹配数据能否将复杂度降为线性？

你的判断非常准确，下面我们从原代码复杂度分析、HashMap优化原理、实际性能对比三个维度来验证这个结论：

一、原代码的时间复杂度分析 #

先看你给出的代码片段核心逻辑：

let filteredPatients = new Array(); 
presencePatients.forEach( patient => { 
  let fhir = fhirPatients.find((fhir)=>{ return fhir.pid === patient.id; }); 
  let bed = bedsInHospital.find(...); // 假设此处为按ID匹配的逻辑
  // 推测还存在departments的find匹配操作
});

结合你给出的参数（presencePatients=100000，fhirPatients=10000，beds=10000，departments=5000）拆解复杂度：

• 外层遍历presencePatients是O(M)，其中M=100000
• 每次遍历内部的fhirPatients.find是O(N)（N=10000），bedsInHospital.find是O(K)（K=10000），departments.find是O(L)（L=5000）
• 整体时间复杂度为 O(M(N+K+L))*，代入数值后是100000*(10000+10000+5000)=2.5×10⁹次操作，属于典型的O(n²)级别算法，数据量越大性能下降越明显

二、HashMap优化的原理与线性复杂度验证 #

在JavaScript中，我们可以用Map对象（或者普通的键值对对象）预先把需要匹配的数据集转换成「键-值」映射表，这样后续匹配时可以通过键直接取值，时间复杂度为O(1)。优化后的代码示例如下：

// 预构建所有需要匹配的映射表（仅需执行一次）
const fhirPatientMap = new Map(fhirPatients.map(fhir => [fhir.pid, fhir]));
const bedMap = new Map(beds.map(bed => [bed.targetId, bed])); // 替换targetId为实际匹配用的键
const deptMap = new Map(departments.map(dept => [dept.targetId, dept])); // 替换targetId为实际匹配用的键

// 遍历匹配，此时所有查找操作都是O(1)
const filteredPatients = presencePatients.map(patient => {
  const matchedFhir = fhirPatientMap.get(patient.id);
  const matchedBed = bedMap.get(/* 对应patient的床匹配键 */);
  const matchedDept = deptMap.get(/* 对应patient的科室匹配键 */);
  // 此处添加你的业务处理逻辑
  return /* 处理后的患者对象 */;
});

复杂度拆解：

• 预构建映射表的时间：O(N+K+L)，也就是10000+10000+5000=25000次操作，这部分耗时几乎可以忽略
• 遍历presencePatients并执行匹配：每次get操作是O(1)，所以这部分时间复杂度是O(M)=100000次操作
• 整体时间复杂度为 O(M+N+K+L)，属于线性时间复杂度O(n)，和原代码的2.5×10⁹次操作相比，性能提升了20000倍左右

三、实际场景的性能差异 #

当数据量越大时，这种优化的效果越显著：

• 原代码：随着presencePatients数量翻倍，总操作量会近似翻倍；如果fhirPatients数量也翻倍，总操作量会变成原来的4倍
• 优化后代码：无论单个数据集的数量如何增长，总操作量都是各数据集大小的线性相加，性能不会出现指数级下降

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