完美哈希是什么？它适合解决什么问题？
简化版
完美哈希是针对一组已知 key 构造无冲突哈希函数，使查找时不需要处理冲突。它适合静态集合，比如关键字表、编译器保留字、只读字典；不适合频繁插入删除的动态场景。
详细版
普通哈希表面对任意输入，冲突不可避免。完美哈希换了前提：key 集合提前已知，可以为这批 key 定制哈希函数。
特点：
- 对已知 key 无冲突。
- 查找可以很快，通常 O(1)。
- 构建阶段可能比较复杂，需要尝试函数或多级结构。
- 一旦 key 集变化，可能要重新构建。
- 适合静态、只读、查询频繁的集合。
面试回答要强调：完美哈希不是通用 HashMap，而是静态集合上的定制化映射。
完整版教学
一、为什么普通哈希表很难保证零冲突
普通哈希表要面对未知输入。key 空间巨大，桶数量有限，根据鸽巢原理，冲突不可避免。
例如 1000 个桶，却可能有无数个字符串 key。无论哈希函数多好，都不能保证任意 key 永远不冲突。
无限或巨大 key 空间 -> 有限桶空间 -> 必然可能冲突完美哈希能做到无冲突，是因为它限制了问题范围：只针对一组已知 key。
二、完美哈希的前提是什么
完美哈希的前提是 key 集合静态或变化很少。比如编译器识别 50 个保留字，路由系统匹配固定命令，嵌入式系统查只读配置项。
当 key 集合已知时，可以不断尝试哈希函数，直到找到一个对这批 key 无冲突的映射。
keys = ["if", "else", "while", "return"]
目标：每个 key 映射到不同槽位这个“为固定集合定制函数”的思路，是它和普通哈希表最大的区别。
三、完美哈希和最小完美哈希有什么区别
完美哈希只要求无冲突，不要求表刚好没有空洞。最小完美哈希要求 n 个 key 映射到 0..n-1，没有冲突也没有空槽。
| 类型 | 要求 | 空间 |
|---|---|---|
| 完美哈希 | 已知 key 无冲突 | 可以有空槽 |
| 最小完美哈希 | 映射到 0..n-1 | 更紧凑 |
| 普通哈希表 | 允许冲突 | 需要冲突处理 |
最小完美哈希更省空间，但构建通常更复杂。工程上要看查询速度、空间和构建成本。
四、构建成本为什么可以接受
完美哈希把成本从查询阶段转移到构建阶段。只要构建不是频繁发生，查询就能长期受益。
例如一个服务启动时花 200 ms 构建固定关键字表，之后处理 10000000 次查询。这个构建成本摊到每次查询上非常小。
构建一次，多次查询如果 key 每秒都在变化，就不适合，因为反复重建会吞掉收益。
五、它和排序数组查找怎么选
静态集合也可以用排序数组 + 二分查找。完美哈希更偏向 O(1) 查询，排序数组更简单且支持范围顺序。
完美哈希：快查存在性或映射值
排序数组：简单、可按序遍历、可范围查询如果只问“这个关键字是否存在”，完美哈希很合适；如果还要按字典序枚举，排序结构可能更自然。
六、动态更新是它的短板
新增一个 key 可能让原本无冲突的函数失效。删除 key 通常容易，但如果集合变化多，继续维护完美性就麻烦。
记忆钩子：完美哈希的完美，只对“已知那批 key”完美；集合一变，完美可能就要重来。
七、常见误区与追问
- 误区：完美哈希适合所有哈希表。 它主要适合静态集合，动态 HashMap 通常不用。
- 误区：完美哈希函数对所有 key 都无冲突。 只保证目标 key 集合无冲突，不保证任意外部 key。
- 误区：最小完美哈希和完美哈希一样。 最小完美哈希还要求映射紧凑到 n 个槽位。
- 追问：为什么编译器关键字适合？ 关键字集合固定，查询频繁，构建一次即可。
- 追问：新增 key 怎么办？ 可能需要重新构建或使用普通哈希结构兜底。
八、加强记忆
完美哈希不是把哈希函数修炼到宇宙无冲突，而是换了题目：key 已知，所以可以定制映射。它适合静态、只读、查询多的场景；动态更新越频繁，它的优势越弱。