O(N×M) 拍平成 O(N+M)：反查表如何把楼层摄像头计数从慢路径救回来

发表于 分类于 ，
「勾这个楼层到底覆盖几个摄像头」——超管在配置页的盲勾体验必须解决。后端用反查表把 O(N×M) 拍平成 O(N+M)，前端零计算渲染，6 个单测全绿。本文把这个看起来简单的功能拆开讲。

「勾这个楼层到底覆盖几个摄像头？」——超管在配置页的盲勾体验必须解决。盲勾的体验很差：要么勾多了（放出不该放的楼层），要么勾少了（后面发现某楼层其实没摄像头，白勾）。

本文把”在 DTO 加一个字段这件事”拆开讲：为什么必须用反查表、为什么计数口径要和 getCameraTree 对齐、为什么保序用 LinkedHashMap、为什么 toMap 要带 merge 函数。前端删 Mock 零计算渲染，后端单测 6/6 全绿。

🎧 文章导读

🎵 背景音乐

反查表算法三步把摄像头按楼层归堆

图1：建反查表 → 按 spaceId 查楼层 → 按楼层 merge 计数，三步完成统计

一、需求背景：两层链路中的”展示性增量”

在拆本次增量之前，先说清整体链路的两层，否则单看本文会摸不着头脑。

1.1 第一层（已合入）：给超管做公司默认可见楼层配置

上一提交 9c7e71ac6 给 super-admin 提供了公司默认可见楼层的配置能力：

  • 新增 GET /cameraInfo/orgFloorConfig/{orgId} 查某公司当前园区已勾选的可见楼层；
  • 新增 POST /cameraInfo/orgFloorConfig 整体保存（空数组即清空，仅超管可操作）；
  • 落库表 security_camera_org_floor 加了唯一约束 (park_id, org_id, floor_space_id)；
  • 保存时先硬删再批插，逻辑干脆。

这套配置是 getCameraTree 可见性过滤的数据源：非超管只能看到所属公司配置楼层下的摄像头，或已审批通过的摄像头编号。

1.2 第二层（本次未提交的增量）：配置页显示「勾这个楼层到底几个摄像头」

配置页面上，超管面对一串楼层勾选框，却不知道「勾下这一栋的 3 楼，到底能看到几个摄像头」。所以本次给配置查询的返回值加了一个 floorCameraCounts 字段，告诉前端每个被勾选楼层下有多少摄像头。

前端要做的事很简单：把三处 Mock 数据（园区、ABC 栋、随机数量）删掉，改为调真实的空间树接口拉当前园区层级，再调配置查询接口回显已勾选楼层与每楼层摄像头数、调保存接口提交。

增量虽小，决策不少。下面把”为什么这样做”的三个关键决策讲清楚。

二、关键决策 1：计数口径必须和 getCameraTree 对齐

2.1 这是整件事的立身之本

getCameraTree 判可见是按楼层放行整个楼层子树——某个楼层被勾选，它下面挂的所有节点（包括房间）里的摄像头全部可见。

那么配置页上「该楼层 N 个摄像头」的 N，就必须是这个楼层子树下的全部摄像头数，否则前端显示的数字和用户实际能看到的数量对不上，超管会被误导。

getCameraTree 与 floorCameraCounts 的口径对齐

图2：左侧 getCameraTree 按楼层放行子树，右侧 floorCameraCounts 必须统计相同子树

2.2 空间模型

摄像头可能直接挂在「楼层」节点上，也可能挂在楼层下的「房间」节点上；而房间节点带 floorId 指回所属楼层。

所以：

1
2
3
「楼层子树的摄像头」
  = 直接挂该楼层的摄像头
  + 挂在该楼层下任意房间的摄像头

这个口径一旦想清楚，算法的骨架就有了：把任意 spaceId 折算成所属楼层 id，再把摄像头按楼层归堆计数。

三、关键决策 2：用反查表而不是嵌套遍历

3.1 最朴素的写法

对每个摄像头，遍历空间树找它属于哪个被勾选的楼层：

1
2
3
4
5
6
7
8
// O(N×M)：N 个摄像头 × M 个被勾选楼层
for (Camera camera : cameras) {
    for (String floorId : floorSpaceIds) {
        if (isInFloorSubtree(camera.getSpaceId(), floorId)) {
            counts.merge(floorId, 1, Integer::sum);
        }
    }
}

空间数和摄像头数一旦都上百，就是 O(N×M) 的嵌套扫描，园区规模一大就慢。

3.2 折中方案：先建反查表

1
2
3
4
5
6
7
8
9
// 反查表：spaceId → 所属楼层 id
Map<String, String> floorBySpace = ...;
// 每个摄像头按 floorBySpace 一次查到楼层 id
for (Camera camera : cameras) {
    String floorId = floorBySpace.get(camera.getSpaceId());
    if (counts.containsKey(floorId)) {
        counts.merge(floorId, 1, Integer::sum);
    }
}

建表 O(空间数)，归堆 O(摄像头数)，**总复杂度 O(空间数+摄像头数)**，一次扫完。

反查表本质上就是把嵌套的查找拍平成一次 Map 预处理。这不是什么高深技巧，但在业务代码里最常被忽略。

四、关键决策 3：LinkedHashMap + merge 函数

4.1 为什么用 LinkedHashMap

前端展示楼层列表要按 floorSpaceIds（被勾选楼层）传入的顺序渲染，不能让 HashMap 的哈希序打乱。

1
2
Map<String, Integer> counts = floorSpaceIds.stream()
        .collect(Collectors.toMap(id -> id, id -> 0, (l, r) -> l, LinkedHashMap::new));

最后一个参数 LinkedHashMap::new 指定底层使用 LinkedHashMap，保证遍历顺序和 floorSpaceIds 一致。

4.2 为什么 toMap 要带 merge 函数

空间数据里如果出现重复 id（理论上不该、实际上可能），Collectors.toMap 默认会抛 merge 异常直接炸接口：

1
java.lang.IllegalStateException: Duplicate key xxx

取 (l, r) -> l（保留先出现的值），容错优先于严格：

1
2
3
4
5
.collect(Collectors.toMap(
    SpaceInfoDTO::getId,
    space -> ...,
    (l, r) -> l    // 脏数据兜底
));

两个小但关键的细节：LinkedHashMap 保序，merge 函数容错。少一个，线上就要炸。

五、核心算法 countCamerasByFloor

5.1 第一步：每个被勾选楼层先初始化为 0

1
2
Map<String, Integer> counts = floorSpaceIds.stream()
        .collect(Collectors.toMap(id -> id, id -> 0, (l, r) -> l, LinkedHashMap::new));

注意初始化用的是被勾选楼层列表（floorSpaceIds），而不是全园区所有楼层——没被勾选的楼层根本不会出现在结果里，这是「只统计被勾选楼层」的第一道关卡。

5.2 第二步：建立 spaceId 到所属楼层 id 的反查表

1
2
3
4
5
6
7
8
Map<String, String> floorBySpace = spaces.stream().collect(Collectors.toMap(
        SpaceInfoDTO::getId,
        space -> DictConstants.SPACE_LEVEL_ROOM.equals(space.getSpaceHierarchy())
                ? StringUtils.defaultString(space.getFloorId())   // 房间 -> 取其 floorId
                : DictConstants.SPACE_LEVEL_FLOOR.equals(space.getSpaceHierarchy())
                    ? space.getId()                                // 楼层 -> 自身
                    : StringUtils.EMPTY,                           // 其它层级 -> 忽略
        (l, r) -> l));

这段三元嵌套是算法的实质：

节点类型 折算结果
房间 取其 floorId 指向的楼层
楼层 自身 id
其它层级（楼栋、园区等） 空串忽略

StringUtils.defaultString 是防空：万一某个房间的 floorId 是 null，兜底成空串，后面 counts::containsKey 自然过滤掉。

5.3 第三步：每个摄像头按 spaceId 归到楼层，只统计被勾选的

1
2
3
4
cameras.stream()
        .map(c -> floorBySpace.get(c.getSpaceId()))
        .filter(counts::containsKey)
        .forEach(floorId -> counts.merge(floorId, 1, Integer::sum));

filter(counts::containsKey) 是第二道关卡：园区里摄像头可能挂在非楼层/非房间（比如挂在楼栋层、或挂在未被该公司勾选的楼层），这些 floorBySpace 折算出来的 id 不在 counts 的 key 集合里，一律不计。

两道关卡叠加，结果就精确等于「被勾选楼层子树下的摄像头数」。

六、getOrgFloorConfig 的改动

6.1 改动点

原来 getOrgFloorConfig 拿到 floorSpaceIds 直接塞进 result 就返回，逻辑很轻。现在要在返回前多干两件事：

  1. 拉本园区全部空间（spaceInfoClient.list）；
  2. 拉本园区全部摄像头（listByCondition(cameraQuery)，按 parkId 过滤）；
  3. 然后交给 countCamerasByFloor 算计数填进 floorCameraCounts。

改动只动了 CameraInfoServiceImpl.java 里这一个方法，以及 DTO 加字段、单测加用例，三处收敛在同一模块，不涉及跨服务。

6.2 为什么「全量拉」而不是「按楼层过滤拉」

[!tip] 性能 vs 可读性的权衡
全量拉空间和摄像头看起来粗放，但这是配置页低频接口、数据量也就一个园区的规模。按楼层过滤反而要为每个勾选楼层发一次查询，N 次 IO 远比一次全量拉慢。用反查表把后续计算压成 O(N+M)，整体反而更快。配置接口不是性能热点，可读性优先。

七、前端接入：零计算

前端在另一个仓库（文件路径以实际仓库为准），本次改动两个文件：

  1. 摄像头楼层配置页面组件：删掉了「园区、ABC 栋、随机数量」三处 Mock 数据，改为调用真实的空间树接口拉当前园区空间层级，再调配置查询接口回显已勾选楼层与每楼层摄像头数、调保存接口提交。
  2. API 定义文件：新增 orgFloorConfig 的 GET/POST 封装，对应后端两个接口。

前端的职责被刻意压到最轻——它只负责拉数据、渲染勾选框和「该楼层 N 个摄像头」的文案、提交勾选结果，零计算。所有计数逻辑都在后端算好，前端拿到 floorCameraCounts 直接按 key 取值渲染。

这和”计数口径要和 getCameraTree 对齐”是配套的：计数是后端的职责，前端不该重复实现一套可能跑偏的口径。

7.1 前端验证

  • ESLint：0 error；
  • 生产构建成功，30 条 warning 均为项目既有问题，与本次改动无关。

八、DTO 改动：只加一个字段

CameraOrgFloorConfigDTO 只加了一个字段，key 是楼层 spaceId、value 是摄像头数：

1
private Map<String, Integer> floorCameraCounts;

字段为什么不复杂化、为什么不单独建一个 DTO？因为它就是「配置查询的附加信息」，和 floorSpaceIds（已勾选楼层列表）同生同灭，没必要拆。这是 YAGNI——单用途的附加字段，塞进现有 DTO 最省事。

九、测试与验证

后端单测 CameraInfoServiceImplTest.java 新增了 cameraCountsIncludeCamerasBoundToRooms 用例，专门验证「直接挂楼层的摄像头 + 挂楼层下房间的摄像头都计入该楼层」这个口径：

  • floor-1 上有一个直接挂楼层的摄像头 + 一个挂 room-1 的摄像头（room-1 的 floorId 指向 floor-1）→ floor-1 计 2；
  • floor-2 无摄像头 → 0。

加上原有用例，后端单测 6/6 全绿。

这个用例的价值在于它锁住了口径——如果以后有人改 countCamerasByFloor 时忘了把房间下的摄像头归到楼层，这个用例会立刻红。

十、经验总结

10.1 两条可复用的经验

[!tip] 经验 1：附加统计字段要对齐主链路口径
本次 floorCameraCounts 必须和 getCameraTree 的可见性判断用同一个口径（楼层子树全计），否则前端显示数和实际可见数对不上。任何「给现有功能加展示性统计」的需求，第一步都是先确认主链路的统计口径，再让附加字段对齐它。

[!tip] 经验 2：嵌套查找先建反查表
O(N×M) 的嵌套遍历，几乎总能用一次 Map 预处理拍平成 O(N+M)。这不是什么高深技巧，但在业务代码里最常被忽略——看到双层循环找归属关系，第一反应就该是「能不能先建个 Map」。

10.2 为什么不过度设计

这次刻意没做这些事：

没做的事 原因
给 countCamerasByFloor 抽接口 只有一个实现、一个调用方，抽了就是死灵活性
给 floorCameraCounts 做分页或懒加载 配置页一次性渲染、数据量就是一栋楼的层级
在 DTO 上加 totalCameraCount 汇总字段 前端要汇总自己 reduce 一下就行，后端不该提供没人要求的字段

每一行改动都能直接追溯到「让超管看到每楼层摄像头数」这一个需求。

10.3 反查表适用的 4 个场景

  1. 空间归属：摄像头属于哪个楼层、设备属于哪个房间——本质都是 spaceId → 父级 id 的映射。
  2. 组织归属：用户属于哪个组织、订单属于哪个事业部——userId/orderId → orgId。
  3. 标签归属：商品属于哪些类目、文章属于哪些话题——商品/文章 id → 标签集合。
  4. 租户归属：资源属于哪个租户——resourceId → tenantId。

判断标准很简单：只要出现”两个集合，每个元素要找它在另一个集合里的归属”的双层循环，就该建反查表。

10.4 算法选型的”够用就好”原则

不要追求”理论最优”，要追求”业务场景下的最优”。本次的全量拉 + O(N+M) 计算，在园区规模下完全够用：

数据规模 性能
空间数 < 1000，摄像头数 < 1000 单次查询 < 50ms
空间数 < 5000，摄像头数 < 5000 单次查询 < 200ms
空间数 > 10000 考虑分园区拉或异步预热

配置接口不是性能热点，可读性优先于理论最优。

十一、结语

「让超管看到每楼层摄像头数」这个需求，看起来只是「在 DTO 加一个字段」，背后却是三个决策：计数口径和主链路对齐、O(N+M) 替代 O(N×M)、保序和容错两个细节。

下次再遇到”展示性统计字段”的需求，按这个顺序思考：

  1. 口径和谁对齐？ 找到主链路的统计口径，让新字段对齐它。
  2. 有没有嵌套查找？ 有就先建反查表。
  3. 需要保序吗？ 需要就用 LinkedHashMap。
  4. 数据可能有脏吗？ 有就给 toMap 加 merge 函数。

算法优化的最高境界不是”我想到了牛逼的算法”，而是”我把嵌套循环换成了一次 Map 预处理”。