什么是哈希洪泛攻击？哈希表如何防御？
简化版
哈希洪泛攻击是攻击者构造大量哈希冲突 key，让哈希表桶内链表变长，使请求处理从平均 O(1) 退化到 O(n)，造成 CPU 飙升。防御包括随机化哈希种子、限制输入规模、桶内树化、使用安全哈希、限流和超时。
详细版
哈希表性能依赖 key 分散。如果攻击者知道某语言或框架的哈希算法，就可能提交大量落到同一桶的参数名。服务器解析表单或 JSON 时不断插入这些 key，冲突链变长，CPU 消耗急剧增加。
正常: key 分散到很多 bucket -> 每桶少量比较
攻击: key 全进同一 bucket -> 插入/查找接近线性工程防御不能只靠“哈希表平均 O(1)”的乐观假设，要考虑恶意输入。
完整版教学
一、攻击利用了哈希表的最坏情况
哈希表平均 O(1)，但前提是哈希分布足够均匀。若大量 key 哈希到同一桶，桶内查找需要逐个比较，链地址法会退化成链表扫描。攻击者提交几万组冲突参数，就可能让一次请求消耗大量 CPU。
这类问题在 Web 表单参数、HTTP header、JSON 字段解析等场景尤其危险，因为 key 往往来自外部输入。
二、为什么攻击者能构造冲突
如果哈希函数固定且公开，攻击者可以离线搜索大量同哈希或同桶 key。对于容量为 1024 的表，只要让低 10 位索引相同，就可能落入同一桶；若扩容策略可预测，攻击成本更低。
bucketIndex = hash(key) & (capacity - 1)
攻击目标: 让很多 key 的 bucketIndex 相同这也是为什么安全场景会引入随机种子，让攻击者无法提前稳定构造冲突。
三、语言和库常见防御
现代运行时通常会做一些防御。例如 Java 8 的 HashMap 在桶内节点超过阈值且容量足够时会树化，把桶内查询从链表 O(n) 降到红黑树 O(log n)。Python、Ruby 等语言对字符串哈希引入随机化，降低跨进程复现冲突的可能。
| 防御 | 作用 | 局限 |
|---|---|---|
| 随机哈希种子 | 让冲突难以预构造 | 不是所有 key 类型都有 |
| 桶内树化 | 降低单桶退化 | 仍有常数和内存成本 |
| 输入限制 | 控制攻击规模 | 需要业务配合 |
单一防御不够，通常要组合使用。
四、业务层要做什么
业务系统不能把所有压力都交给 HashMap。入口层应限制参数数量、字段名长度、请求体大小和解析时间；对异常高冲突或异常大请求做拒绝、限流或降级。
例如表单参数最多 1000 个、单个 key 最长 128 字符、请求体最大 1MB。即使底层哈希退化，攻击面也被输入上限压住。
五、如何排查疑似哈希洪泛
症状通常是单机 CPU 高、请求体不大但解析耗时异常、热点接口集中在参数解析或 Map 插入。可以从访问日志中找字段数量异常、重复模式 key、单请求耗时和 GC/CPU profile。
排查路径:
慢请求样本 -> 请求参数数量/长度 -> CPU profile -> Map put/get 热点 -> 输入限制与拦截如果只是普通业务热点，不应误判为哈希攻击；要结合外部输入模式和冲突证据。
六、常见误区与追问
记忆钩子：哈希洪泛打的不是内存容量，而是“把 O(1) 打回 O(n)”的 CPU 账单。
- 误区：哈希表平均 O(1)，所以不用担心。 安全问题看恶意最坏情况，不看平均随机输入。
- 误区：扩容一定能解决冲突。 攻击者可以构造在新容量下仍同桶的 key，且扩容本身也有成本。
- 误区：树化后就绝对安全。 树化降低退化程度，但输入规模、比较成本和内存仍可能被打满。
- 追问：随机哈希种子有什么用？ 让攻击者无法离线稳定预测冲突 key。
- 追问：业务最有效的第一道防线是什么？ 限制请求体大小、参数数量和字段长度。
- 追问：和普通哈希冲突有什么区别？ 普通冲突是偶然分布，哈希洪泛是恶意批量构造冲突。
七、加强记忆
哈希洪泛的本质是利用哈希表最坏复杂度：大量 key 挤进同一桶，让插入和查找退化。防御要分三层：哈希算法随机化、数据结构退化保护、入口输入限制和限流。面试回答时把“攻击原理 -> 退化后果 -> 多层防御”说完整。