Cal.com 中的重复查找优化：用索引 Map 把 O(n) .find() 变成 O(1) 查询

本篇围绕 Cal.com 仓库（cal.diy）内置的 Vercel React Best Practices 规则文件 js-index-maps.md 展开，讲解"为重复查找构建索引 Map"这一 JavaScript 性能优化模式：为什么循环内反复调用 .find() 会退化成平方级复杂度，如何用一次 O(n) 的 Map 构建换来后续所有 O(1) 查询。读完你可以掌握该模式的判定标准、正确写法、边界处理（键归一化、缺失键、重复键），并能在 Cal.com 的真实源码中看到这套模式在预订查询、审计追踪、黑名单校验等模块中的落地方式。

规则定位：Vercel React Best Practices 中的 js- 类别

该规则是仓库内 SKILL.md 所描述的 45 条性能优化规则之一。技能按影响程度将规则划分为 8 个优先级类别，其中 js- 前缀属于第 7 类"JavaScript Performance"（LOW-MEDIUM），与 js-set-map-lookups、js-combine-iterations、js-cache-property-access 等规则并列：

优先级	类别	影响	前缀
1	Eliminating Waterfalls	CRITICAL	async-
2	Bundle Size Optimization	CRITICAL	bundle-
3	Server-Side Performance	HIGH	server-
4	Client-Side Data Fetching	MEDIUM-HIGH	client-
5	Re-render Optimization	MEDIUM	rerender-
6	Rendering Performance	MEDIUM	rendering-
7	JavaScript Performance	LOW-MEDIUM	js-
8	Advanced Patterns	LOW	advanced-

虽然整体优先级为 LOW-MEDIUM，但该规则元数据中给出的量化影响很直观：impactDescription: 1M ops to 2K ops。也就是说，在中等数据规模下，这条规则的收益仍然可以从百万次比较压缩到两千次操作，属于"改动一行、收益显著"的低成本优化。

问题场景：循环内对同一键反复 .find()

规则文档给出的反模式是"用同一个键做多次 .find() 查找时，应该改用 Map"。其错误示例如下：

function processOrders(orders: Order[], users: User[]) {
  return orders.map(order => ({
    ...order,
    user: users.find(u => u.id === order.userId)
  }))
}

这里的问题在于：orders.map() 每处理一个订单，就会对整个 users 数组执行一次线性的 find() 扫描。Array.prototype.find 的时间复杂度是 O(n)，而它又被执行了 m 次（m 为订单数），总复杂度就是 O(n × m)——这是典型的"隐式平方级"开销：单看每行代码都很短，组合起来却在循环里做了嵌套遍历。

文档给出的量化结论可以直接继承：构建一次 Map 是 O(n)，之后的每次查找都是 O(1)；对 1000 个订单 × 1000 个用户的场景，操作量从 1M（100 万次）降到 2K（2000 次）。这正是 impactDescription 字段数字的由来。

正确写法：一次建索引，处处 O(1) 查询

规则给出的正确示例：

function processOrders(orders: Order[], users: User[]) {
  const userById = new Map(users.map(u => [u.id, u]))

  return orders.map(order => ({
    ...order,
    user: userById.get(order.userId)
  }))
}

写法分两步，可以拆解为三个要点：

1. 索引构建只做一次。new Map(users.map(u => [u.id, u])) 用一个数组推导把 id -> user 的映射整体灌入 Map，这一步是 O(n) 的一次性成本；
2. 查找全部走 Map.get()。Map 内部基于哈希表实现，get() 平均为 O(1)，与数组长度无关；
3. 总体复杂度从 O(n × m) 降为 O(n + m)。构建索引 O(n) + 查询 O(m × 1)，两项相加而非相乘。

这一模式成立的前提也很明确：查找必须发生在循环里，且查询键来自同一个集合。如果只是对数组做一次性的 .find()，直接调用即可，构建 Map 反而是多余的内存开销。

Cal.com 源码中的真实落地

在 Cal.com 仓库中，"先建 Map、后循环查询"是服务端数据装配的高频写法。以下几处实现均完整体现了该规则描述的模式（构建 Map 与消费 Map 分离、键为业务主键）：

1. 预订输出服务：按 ID 批量回查预订

output.service.ts 的 getOutputRecurringBookings 需要按传入的 bookingsIds 顺序输出预订，但数据库按集合返回记录，顺序无法保证。实现方式是先建索引、再按键取出并显式处理缺失：

const bookingsMap = new Map(databaseBookings.map(booking => [booking.id, booking]));

const transformed = bookingsIds.map(bookingId => {
  const databaseBooking = bookingsMap.get(bookingId);
  if (!databaseBooking) {
    throw new Error(`Booking with id=${bookingId} was not found in the database`);
  }
  return this.getOutputRecurringBooking(databaseBooking);
});

这里的 if (!databaseBooking) throw ... 值得注意：Map.get() 对不存在的键返回 undefined 而不是抛错，因此**"期望键一定存在"的场景必须自行做缺失检测**。这是该规则原文示例未展开、但生产代码必须补上的边界。

2. 审计记录回填操作人：先聚合唯一键，再一次查询

AdminWatchlistQueryService.ts 在展示审计列表时，需要为每行 latestAudit.changedByUserId 回填用户对象。其流程是该模式的完整"教科书版"：

const userIds = rows
  .map((entry) => entry.latestAudit?.changedByUserId)
  .filter((id): id is number => id !== null && id !== undefined);

const uniqueUserIds = Array.from(new Set(userIds));

const users = uniqueUserIds.length > 0 ? await this.deps.userRepo.findUsersByIds(uniqueUserIds) : [];

const userMap = new Map(users.map((u) => [u.id, u]));

const rowsWithCreators = rows.map((entry) => {
  if (entry.latestAudit?.changedByUserId) {
    const changedByUser = userMap.get(entry.latestAudit.changedByUserId);
    // ...回填 changedByUser
  }
  return entry;
});

这段代码把索引 Map 和另外两个优化叠加了起来：先用 Set 对 userIds 去重（对应姊妹规则 js-set-map-lookups.md 中"重复成员判断用 Set"的思想），再一次批量查询、再一次建 Map。同文件 L105-L110 的 getWatchlistEntryDetails 对审计历史做了同样的 userMap.get() 回填，说明该模式在同类逻辑中被一致复用。

3. No-Show 任务：用邮箱做键的索引

triggerHostNoShow.ts 在标记未入会主持人时，把参会人列表按邮箱建索引，随后在异步更新循环里按 host.email 直接取对应记录：

const attendeesBefore = await attendeeRepository.findByBookingId(booking.id);
const attendeesBeforeByEmail = new Map(attendeesBefore.map((a) => [a.email, a]));
// ...
const attendeeBefore = attendeesBeforeByEmail.get(host.email);

这里暴露出 Map 键选择的一个实战考量：键必须是查找侧和被索引侧"完全一致"的原始值。邮箱类键对大小写、首尾空格敏感，如果两侧来源不同（一个是入库值、一个是外部会议系统回传值），get() 会静默返回 undefined。

4. 键归一化的对照案例

Cal.com 的黑名单校验恰好给出了"归一化"的标准做法。check-user-blocking.ts 在 fail-open 兜底分支中，把邮箱统一做 trim().toLowerCase() 后再作为 Map 键：

return new Map(emails.map((e) => [e.trim().toLowerCase(), false]));

同文件 L86-L94 的 getBlockedUsersMap 注释也点明了目的："Single DB query for N emails - eliminates N+1"——对 N 个邮箱只做一次查询，再靠 Map 完成逐条回查。也就是说，当业务键天然带有格式噪声时，构建 Map 之前先做键归一化（去空格、统一大小写），是保证 get() 命中率的前提，否则索引建得再快也查不中。

其他一致的实现

仓库中同型模式还有不少，可作进一步检索的入口：

• users.repository.ts：new Map(users.map((user) => [user.id, user.defaultScheduleId]))，用 ID 索引用户的默认日程；
• CalendarService.ts：Google Calendar 集成中按日历 ID 索引时区，new Map(calIdsWithTimeZone.map((cal) => [cal.id, cal.timeZone]))；
• FeatureOptInService.ts：按 feature.slug 索引功能开关状态；
• getEventTypesByViewer.ts：enrichedUsersMap 按用户 ID 索引富化后的用户对象。

从源码结构看，这些位置都符合"批量取回数据 + 循环内按业务键回填"的装配场景，与规则文档描述的应用场景一一对应。

与姊妹规则 js-set-map-lookups 的分工

同一 js- 类别下还有 js-set-map-lookups.md，两者常被混用，边界如下：

规则	数据结构	解决的问题	典型 API
js-set-map-lookups	Set	重复的成员判断，array.includes(x) 是 O(n)	new Set(ids) + .has(x)
js-index-maps（本文主题）	Map	按键取出值对象，array.find(u => u.id === k) 是 O(n)	new Map(arr.map(u => [u.id, u])) + .get(k)

判断口诀：只要答案是"在不在"，用 Set；答案是"对应的那个对象是什么"，用 Map。AdminWatchlistQueryService.ts 中先 Array.from(new Set(userIds)) 去重、再 new Map(...) 建索引的连续写法，正是两条规则组合运用的实例。

适用边界与实践要点

把规则文档与仓库实践合并起来，可以得到一份可直接用于代码评审的判定清单：

1. 值得建索引的条件：查找发生在循环内，且被查找数组在一次函数执行中不变。一次性查找、或数组长度极小（个位数）时，.find() 的常数开销可忽略，建 Map 反而增加内存与代码噪音；
2. 键的唯一性：Map 的键冲突时后写入者覆盖先写入者。若源数据中键可能重复（例如按邮箱索引而存在大小写变体），需要在构建前归一化或显式去重，否则索引内容不确定；
3. 键的归一化：字符串键（邮箱、slug、URL）务必在两侧使用完全一致的规范化形式，参考 check-user-blocking.ts 的 trim().toLowerCase()；
4. 缺失键必须显式处理：Map.get() 查不到时返回 undefined，"键应必然存在"的路径（如 output.service.ts 的按 ID 回查）应抛错或降级，"键可能不存在"的路径（如审计回填）则把 undefined 作为合法业务值处理；
5. 与批量查询搭配：索引 Map 通常紧跟一次"聚合唯一键 -> 批量查询 -> 建 Map -> 循环回填"的流程（见 AdminWatchlistQueryService.ts），这与"单次 DB 查询消除 N+1"的目标是同一件事的两面：Map 消除了内存里的 N+1，批量查询消除了数据库里的 N+1。

小结

js-index-maps.md 这条规则的核心只有一句话：对同一键的多次 .find() 应改为一次 Map 构建加 O(1) 的 .get()，把 O(n × m) 降到 O(n + m)，官方示例的量化收益是 1000 × 1000 场景下从 1M 次操作降到 2K 次。Cal.com 的预订输出、审计回填、No-Show 标记与黑名单校验等服务端代码中反复出现这一模式，并额外示范了规则原文未展开的三处工程细节——缺失键的显式抛错、字符串键的归一化、以及"Set 去重 + 批量查询 + Map 索引"的完整装配链。在评审或重构数据装配代码时，只要看到"循环 + .find()/.includes() + 稳定数据源"的组合，就可以套用该模式，并以本文列出的仓库内实现作为对照基准。