完美哈希：从理论到 gperf 实践
内容提要
本文讨论了完美哈希在编程语言关键字识别中的应用，完美哈希函数确保零冲突，查找时间为O(1)。GCC使用gperf生成C/C++关键字的完美哈希函数。文章介绍了FKS方案、最小完美哈希及其构造算法，如CHD和RecSplit，强调了完美哈希在静态字典问题中的优势，适用于高频查找和确定性延迟的场景。
关键要点
-
完美哈希函数确保零冲突，查找时间为O(1)。
-
GCC使用gperf生成C/C++关键字的完美哈希函数。
-
完美哈希适用于静态字典问题，特别是在高频查找和确定性延迟的场景中。
-
FKS方案是第一个理论上最优的完美哈希方案，空间复杂度为O(n)，查找时间为O(1)。
-
最小完美哈希（MPHF）将n个键双射到[0,n)，其空间下界约为1.44 bits/key。
-
CHD算法是实用的MPHF构造方法，空间复杂度为2.07 bits/key，构造时间为O(n)。
-
RecSplit算法接近理论下界，空间复杂度为1.56 bits/key，构造时间为O(n log n)。
-
gperf是为小规模静态字符串集合生成完美哈希函数的标准工具，广泛应用于编译器中。
-
完美哈希在编译器关键字识别、HTTP头部解析、静态路由表等场景中有重要应用。
延伸问答
完美哈希函数的主要特点是什么？
完美哈希函数确保零冲突，查找时间为O(1)。
gperf工具的主要用途是什么？
gperf是为小规模静态字符串集合生成完美哈希函数的标准工具，广泛应用于编译器中。
什么是最小完美哈希函数（MPHF）？
最小完美哈希函数将n个键双射到[0,n)，其空间下界约为1.44 bits/key。
FKS方案的核心思想是什么？
FKS方案通过两级哈希结构，将n个键分到m个桶中，允许冲突，然后在每个桶内使用独立的哈希函数消除冲突。
CHD算法的主要步骤是什么？
CHD算法包括三个步骤：哈希、位移和压缩，用于构造最小完美哈希函数。
完美哈希适合哪些场景？
完美哈希适合静态键集合、高频查找和需要确定性延迟的场景，如编译器关键字识别和静态路由表。
