知识卡片
最小完美哈希函数：为静态字典预先消灭哈希冲突
内容
普通哈希表几乎注定遇到冲突——即使装载因子保守，冲突概率也高得反直觉（生日悖论：365个槽，23个键值冲突概率就超过50%），因此常规哈希表要额外设计冲突处理机制。最小完美哈希函数换个思路：若字典词条提前已知且固定，可针对该集合预先计算专属哈希函数，让每个词精确映射到互不重复的位置，从数学上根除冲突。代价是换一批词就要重新构造，只适合字典基本静态、查询远比更新频繁的场景。
参考来源
- 位置：第4章《查询》「最小完美哈希函数」小节（源文件：_chapter-text/ch04.txt）
- 结论依据：原文用生日悖论说明哈希冲突概率远超直觉，并定义完美哈希函数为对固定键值集合完全无冲突的哈希函数，直接支持卡片论点。
- 原始内容："最好的例子莫过于著名的生日悖论（birthday paradox）了……给定一个365个哈希槽，随机选择多少个键值才能够使得出现冲突的概率超过0.5？……答案是只需区区23人……这就是完美哈希函数（perfect hash function）。这里，当对一个键值集合L进行哈希时，不可能出现任何冲突。"