cal.diy 性能实践：用 Set/Map 实现 O(1) 查找——从 vercel-react-best-practices 规则到预订流程中的真实落地

cal.diy 性能实践：用 Set/Map 实现 O(1) 查找——从 vercel-react-best-practices 规则到预订流程中的真实落地

【免费下载链接】cal.diyScheduling infrastructure for absolutely everyone.项目地址: https://gitcode.com/GitHub_Trending/ca/cal.diy

本文基于 cal.diy 仓库中的性能规则文档 .opencode/skill/vercel-react-best-practices/rules/js-set-map-lookups.md，完整讲解"用 Set/Map 替代数组进行 O(1) 成员判断"这一 JavaScript 性能规则的写法、复杂度原理与适用边界，并结合预订（booking）核心链路中的真实源码，展示该模式在 cal.diy 中如何被反复应用，帮助你在评审或重构代码时快速识别"嵌套 includes/find 造成的 O(n²) 隐患"。

规则定位：vercel-react-best-practices 中的 JavaScript 性能条目

该规则文件隶属于 Vercel 出品的 React/Next.js 性能优化技能集 SKILL.md（同仓库另有一份镜像位于 agents/skills/vercel-react-best-practices/SKILL.md）。该技能集共包含 45 条规则、8 个类别，按影响优先级分层管理。文档的 frontmatter 明确标注了本规则的元信息：

title: Use Set/Map for O(1) Lookups impact: LOW-MEDIUM impactDescription: O(n) to O(1) tags: javascript, set, map,>const allowedIds = ['a', 'b', 'c', ...] items.filter(item => allowedIds.includes(item.id))

Array.prototype.includes在每次调用时都要从数组头部开始线性扫描，直到命中或遍历结束。外层filter对items的每个元素都触发一次这样的扫描，因此总代价是items.length × allowedIds.length——两个列表各自增长时，复杂度按乘积（二次方）恶化。

正确写法（每次检查 O(1)）：

const allowedIds = new Set(['a', 'b', 'c', ...]) items.filter(item => allowedIds.has(item.id))

Set基于哈希表实现，has()平均时间复杂度为 O(1)。构建 Set 本身需要一次 O(n) 遍历，但只需付一次；之后无论items有多长，每次判断都是常数时间。整体复杂度从 O(n × m) 降为 O(n + m)。

从源码结构看复杂度为什么重要：重复成员判断的典型形态

这条规则真正的杀伤力体现在嵌套循环内的查找。可以推断 cal.diy 的预订链路恰好是这类场景的高发区：一次新预订需要把"候选主持人群""回退主持人群""固定主持人群"分别与"用户全量列表"做交集，如果每轮都用includes/find，就是标准的双重循环。

在 loadAndValidateUsers.ts 中，源码正是规则文档的逐字落地：

if (qualifiedRRHosts.length) { // remove users that are not in the qualified hosts array const qualifiedHostIds = new Set(qualifiedRRHosts.map((qualifiedHost) => qualifiedHost.user.id)); qualifiedRRUsers = users .filter((user) => qualifiedHostIds.has(user.id)) .map((user) => ({ ...user, credentials: allQualifiedHostsHashMap[user.id].user.credentials })); } if (allFallbackRRHosts?.length) { const fallbackHostIds = new Set(allFallbackRRHosts.map((fallbackHost) => fallbackHost.user.id)); allFallbackRRUsers = users .filter((user) => fallbackHostIds.has(user.id)) // ... } if (fixedHosts?.length) { const fixedHostIds = new Set(fixedHosts.map((fixedHost) => fixedHost.user.id)); fixedUsers = users .filter((user) => fixedHostIds.has(user.id)) // ... }

三段代码完全对应文档中的"先new Set(...)、再filter(item => set.has(...))"模板。值得注意的是源码先用if (xxx.length)做了空判断再构建 Set——这正是同一技能集中js-length-check-first规则的体现：无数据时连 O(n) 的构建成本都不付出。

同类模式在预订服务中反复出现，可以确认它已被当作团队内的通用写法：

• getLuckyUser.ts：先const availableUserIds = new Set(availableUsers.map((user) => user.id))，之后在筛选主持人与判断可用用户时直接availableUserIds.has(host.user.id)；
• RegularBookingService.ts：const userIdsSet = new Set(users.map((user) => user.id))后以userIdsSet.has(host.user.id)做判断，同一文件中 L850 还有对参与者邮箱构建attendeeEmailSet的用法；
• crmManager.ts：const contactSet = new Set(contacts.map((c: { email: string }) => c.email))，以邮箱为键去重与查存在；
• getTeamsForFeature.handler.ts：tRPC 路由里用hasFeature: assignedTeamIds.has(team.id)为每个团队标注特性归属，替代了逐团队遍历比对；
• getEventTypesFromGroup.handler.ts：isCurrentUserHost: eventTypeIdsWhereUserIsHost.has(eventType.id)，在列表渲染前批量打标签。

这些位置的共同点是：在渲染或批量处理之前，把"成员关系"预先编译成一次 O(1) 查询，而不是在 map/filter 回调里对每个元素重复线性扫描。

姊妹规则 Map 场景：find到Map.get的升级

js-set-map-lookups只讲了一半（Set 判断存在性），完整图景需要结合同类的 js-index-maps.md 理解：当需要取回"查到的值"而不只是判断"存不存在"时，应该用 Map 而不是反复.find()。

js-index-maps 给出的对照是：

// Incorrect (O(n) per lookup) function processOrders(orders: Order[], users: User[]) { return orders.map(order => ({ ...order, user: users.find(u => u.id === order.userId) })) } // Correct (O(1) per lookup) 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) })) }

文档中给出了量化口径："Build map once (O(n)), then all lookups are O(1)。For 1000 orders × 1000 users: 1M ops → 2K ops。" 即 1000 单 × 1000 用户的场景，操作量从约 100 万次降到约 2000 次。

cal.diy 源码中也能找到 Map 查值的真实实例：loadAndValidateUsers.ts 在filter之后紧跟.map((user) => ({ ...user, credentials: allQualifiedHostsHashMap[user.id].user.credentials }))，从源码结构看allQualifiedHostsHashMap是预先构建的以user.id为键的哈希索引，避免在 map 回调里再次按 id 线性查找——Set 与 Map 在同一段逻辑里分工明确：Set 负责"筛谁留下"，Map 负责"为留下的元素取值"。

此外，heavy/update.handler.ts 展示了第三种变体：用Map的键集合做存在性判断（existingGroupsMap.has(group.id)），以此把一组 host groups 三分为 toCreate / toUpdate / toDelete。由于Map.has(key)与Set.has(value)同为 O(1)，当"键→值"映射本来就要使用时，直接复用 Map 判断键是否存在即可，无需再额外构建一个 Set。

适用边界与注意事项

结合规则文档与仓库用法，可以总结以下适用前提，避免把这条规则机械化地到处套：

1. "重复"是前提。Set/Map 的构建有 O(n) 一次性成本。如果成员判断只执行一次（比如只includes一次固定小数组），线性扫描可能反而更快，不必构建哈希结构。该规则的impact: LOW-MEDIUM定级正源于此。
2. 键必须可哈希且稳定。Set/Map以值（原始值按值、对象按引用）判断相等。cal.diy 源码中所有实例都以字符串 id 或邮箱（如 triggerGuestNoShow.ts 中以小写邮箱为键）作键，均为原始值；若要用对象本身作键，需先确认"同一实体引用是否稳定"，否则会误判为不同元素。
3. 大小写/规范化要一致。例如 sendAwaitingPaymentEmail.ts 构建邮箱 Set 时统一.toLowerCase()，否则判断会因大小写差异漏判——哈希结构放大了预处理不一致的代价。
4. 与合并遍历配合。若同一段代码里对同一数组做多次 filter/map，应参考同级的js-combine-iterations规则合并成一次遍历，Set/Map 解决的是"单次判断成本"，合并遍历解决的是"重复遍历成本"，两者正交、可叠加。

小结

Use Set/Map for O(1) Lookups 是一条低门槛、高收益的规则：把arr.includes(x)换成new Set(arr).has(x)、把反复.find()换成Map.get()，即可将批量处理从二次方拉回线性。cal.diy 在预订链路（loadAndValidateUsers.ts、getLuckyUser.ts、RegularBookingService.ts）与 tRPC 路由（getTeamsForFeature.handler.ts）中的实现，正是这套模板在生产代码中的标准落法：先判断集合非空，一次性构建 Set/Map，随后所有元素级判断全部走 O(1) 哈希查询。

【免费下载链接】cal.diyScheduling infrastructure for absolutely everyone.项目地址: https://gitcode.com/GitHub_Trending/ca/cal.diy