JavaScript 性能优化用 Set/Map 替代数组 includes 实现 O(1) 查找Polar 前端实战【免费下载链接】polarPolar — A billing platform for the intelligence era项目地址: https://gitcode.com/GitHub_Trending/po/polar本技术指南基于 Polar 仓库内置的 Vercel 工程团队性能优化规则集.agents/skills/vercel-react-best-practices中js-set-map-lookups规则展开。它解决的是前端开发中一个高频问题对数组执行重复的成员检查includes、find、indexOf时如何在数据规模增长后依然保持稳定性能。读完本文你将掌握 Set/Map 与数组在查找语义上的本质差异、O(n)→O(1) 的复杂度原理以及它们在 React 状态管理、数据去重、跨页选择等真实场景中的落地写法并看到 Polar 前端代码库中的对应实现证据。规则出处与定位js-set-map-lookups规则位于 Polar 仓库.agents目录下的 Vercel React/Next.js 最佳实践技能包中规则正文见 rules/js-set-map-lookups.md其元信息如下元数据字段值titleUse Set/Map for O(1) LookupsimpactLOW-MEDIUMimpactDescriptionO(n) to O(1tagsjavascript, set, map,>// Incorrect (O(n) per check) const allowedIds [a, b, c, ...] items.filter(item allowedIds.includes(item.id))Array.prototype.includes()的语义是从数组头部开始逐个比较元素直到命中或遍历完毕。因此单次includes的最坏时间复杂度为 O(n)n 为数组长度将includes放进filter回调后整体复杂度变为O(m × n)m 为items长度n 为allowedIds长度随着两个数组的规模增长总操作次数呈二次方膨胀。类似的线性扫描方法还包括Array.prototype.indexOf()用于查找下标和Array.prototype.find()用于按条件查找对象见姊妹规则 js-index-maps.md。解决方案Set.has() 实现 O(1) 成员检查规则给出的正确写法// Correct (O(1) per check) const allowedIds new Set([a, b, c, ...]) items.filter(item allowedIds.has(item.id))Set 是基于哈希表实现的集合抽象Set.prototype.has()通过哈希定位平均时间复杂度为 O(1)不随集合规模增长构建 Set 本身是一次 O(n) 的初始化但只需执行一次之后所有成员检查都是常量时间整体复杂度从 O(m × n) 降为O(m n)。何时值得转换重复检查同一份白名单 / 黑名单 / 已存在 id 集合被多次查询循环内、filter 内、多个组件共享数据规模可观数据量达到数十到数百以上且查询次数明显多于集合构建次数集合只读构建完成后不再频繁增删若需要频繁增删Set 的add/delete同样是 O(1)依然优于数组操作。如果只做一次查找[a,b].includes(x)与new Set([a,b]).has(x)的差异微乎其微此时为了可读性保留数组即可——这正是该规则 impact 评级为 LOW-MEDIUM 的原因优化应发生在重复场景而非单次场景。Set 与 Map 如何选择规则标题同时提到 Set 与 Map二者的适用语义不同需求数据结构关键 API只关心某个值是否存在成员检查SetThas(value)、add、delete、size需要按 key 取回对应的 value键值映射MapK, Vget(key)、has(key)、set、delete做白名单过滤、去重、存在性判断时用Set做按 id 索引对象、把 O(n) 的find变成 O(1) 的get时用Map。姊妹规则用 Map 构建索引映射当需要按相同 key 反复执行find时对应的是js-index-maps规则rules/js-index-maps.md// Incorrect: orders.map 里每次 find 都是 O(n) const userById users // ❌ function processOrders(orders, users) { return orders.map(order ({ ...order, user: users.find(u u.id order.userId) })) } // Correct: 一次构建 Map后续 get 都是 O(1) function processOrders(orders, users) { const userById new Map(users.map(u [u.id, u])) return orders.map(order ({ ...order, user: userById.get(order.userId) })) }该规则的 impactDescription 是 1M ops to 2K ops对 1000 个订单 × 1000 个用户的关联查找数组find方案需要 100 万次比较而 Map 索引方案只需构建一次1000 次写入 1000 次 O(1) 读取即约 2000 次操作。这与js-set-map-lookups构成互补Set 解决是否存在Map 解决取到对应值。Polar 仓库中的真实落地规则不是纸面理论——Polar 前端clients/apps/web在多处实践了 Set/Map 查找优化以下是可直接对照的源码证据。案例一useAtRisk —— Set 去重避免重复标记订阅clients/apps/web/src/components/Customer/useAtRisk.ts 中钩子同时拉取past_due逾期与canceling正在取消两类订阅需要保证一个订阅只出现在一个分组里。实现先用 Set 收集逾期订阅 id再对取消中的订阅做 O(1) 成员检查const items useMemoAtRiskItem[](() { const pastDueItems (pastDue?.items ?? []).map((subscription) ({ subscription, reason: past_due as const, })) const pastDueIds new Set(pastDueItems.map((item) item.subscription.id)) const cancelingItems (canceling?.items ?? []) .filter((subscription) !pastDueIds.has(subscription.id)) // O(1) 检查 .map((subscription) ({ subscription, reason: canceling as const, })) return [...pastDueItems, ...cancelingItems].slice(0, limit) }, [pastDue, canceling, limit])这正是规则中Set.has()替代数组includes的标准形态pastDueIds在构建后于 filter 回调中被反复查询。同时它被包在useMemo中仅当pastDue/canceling/limit变化时才重建避免每次渲染重复构建 Set。案例二useSelection —— Map 作为跨页选择索引clients/apps/web/src/hooks/useSelection.ts 维护一张 id → item 的选择映射并用Map.get/Map.has做 O(1) 读取const selected useMemo(() { const onPage new Map(ids.map((id, index) [id, items[index]])) return Array.from(state.map, ([id, item]) onPage.get(id) ?? item) }, [state, items, ids]) const pageSelectedCount useMemo(() { let selectedCount 0 for (const id of ids) { if (state.map.has(id)) { selectedCount } } return selectedCount }, [ids, state])在selected的归并计算中onPage.get(id)是 O(1) 的索引读取pageSelectedCount对每页所有 id 做state.map.has(id)检查——如果改用数组这一循环会退化为 O(n²)。此外 useSupportCaseChat.ts 也用new Map(messages.map((message) [message.id, message]))一次构建消息索引供后续 O(1) 取回。案例三迁移向导选择状态 —— Set 承载海量行 idclients/apps/web/src/app/(main)/dashboard/[organization]/(header)/settings/migrations/selection.ts 实现了一个 Gmail 风格的跨页选择模型行 id 可能远超客户端能枚举的量因此选择状态只保留被剔除/被勾选的差异集用Setstring承载export interface SelectionState { mode: SelectionMode // all | none toggled: Setstring } export function isRowSelected(state: SelectionState, id: string): boolean { return state.mode all ? !state.toggled.has(id) : state.toggled.has(id) } export function selectedCount(state: SelectionState, importableTotal: number): number { const count state.mode all ? importableTotal - state.toggled.size : state.toggled.size return Math.max(0, count) }这里 Set 的优势体现得淋漓尽致对任意行 id 的选中判断是 O(1) 的hassize属性 O(1) 给出数量而toggleRow通过new Set(state.toggled)复制后add/delete保持不可变更新。配套测试 selection.test.ts/dashboard/[organization]/(header)/settings/migrations/selection.test.ts) 直接以toggled: new Set(ids)构造状态断言行为。如果改用数组存储待排除 idisRowSelected将退化为 O(n) 的includes在海量行场景下会显著拖慢表格渲染。案例四sitemap 去重clients/apps/web/src/app/sitemap.ts 在生成站点地图时用...new Set([...collectLandingRoutes(), ...EXTRA_ROUTES])去重利用 Set 保证路由唯一性后再展开回数组——这是 Set 作为去重中间结构的常见用法。在 React 状态中使用的注意事项Polar 源码展示了在 React 中安全使用 Set/Map 的几个关键约束保持不可变更新不要直接setToggled.add(id)而是setToggled(prev new Set(prev).add(id))。useSelection.ts的applySelection与 migration selection 的toggleRow都是先复制再修改这保证 React 能感知状态变化、触发重渲染用 useMemo 缓存构建成本Set/Map 的构建本身是 O(n)放在useMemo中避免每次渲染重复构建如useAtRisk.ts的做法注意引用变化new Set()/new Map()每次都会产生新引用作为 effect 依赖时会导致依赖频繁变化需谨慎这正是useSelection.ts中state.map的取舍。总结与自查清单js-set-map-lookups规则给出的是一条低成本、高确定性的优化路径适用判断非常简单见arr.includes(x)/arr.indexOf(x)/arr.find(...)出现在循环、filter、map、高频渲染或共享工具函数中 → 先问这个查找会重复多少次重复次数多 → 在循环外一次性构建Set存在性或Map取回值把每次查询从 O(n) 降为 O(1)在 React 中遵循不可变更新 useMemo缓存参考 useAtRisk.ts 与 useSelection.ts 的实现风格。该规则与js-index-mapsMap 索引、js-cache-property-access循环内缓存属性、js-combine-iterations合并遍历共同构成了 JavaScript 性能优化的基础工具箱完整规则目录见 rules 目录总览见 AGENTS.md。【免费下载链接】polarPolar — A billing platform for the intelligence era项目地址: https://gitcode.com/GitHub_Trending/po/polar创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考