【问 chatGPT 】如何计算 perfect hash

作者:张富春(ahfuzhang)，转载时请注明作者和引用链接，谢谢！

• cnblogs博客
• zhihu
• Github
• 公众号:一本正经的瞎扯
  

---

假定已知存在 N 个不同的值，如何设计一个 hash 函数，使得这些值在 hashtable 中严格的实现 O(1) 时间复杂度的查询？
实际上，很多编译器把 switch 的很多个分支上的常量，计算出一个 perfect hash，然后运行期的代码就可以使用 O(1) 的时间复杂度来跳转，从而提升性能。

有这样一些场景就可以使用 perfect hash 来优化：例如配置项，通常可能是 1 分钟加载一次，然后就不再变更，并且在程序中高频使用。
为此，就可以为大量的配置值计算 perfect hash，以便在运行期获得最好的性能。

下面是一个字符串计算 perfect hash 的例子：

package mainimport ("fmt"
)// 一个简单的 64bit hash（FNV1a 的变体，带 seed）
// 真实项目里你可以换成 xxhash、siphash 等更强的 hash。
func hashStringWithSeed(s string, seed uint64) uint64 {const (offset64 = 14695981039346656037prime64  = 1099511628211)h := offset64 ^ seedfor i := 0; i < len(s); i++ {h ^= uint64(s[i])h *= prime64}return h
}// BuildPerfectHash 尝试为给定的 keys 找到“无碰撞”的一组 hash 值。
// 返回：
//   - hashes: 与 keys 等长的 []uint64，每个 key 一个 hash 值
//   - iter:   第几轮 seed 尝试才成功（从 1 开始）
//
// 注意：
//   - 这个例子只是演示 perfect hash 的“构造过程”，不是 minimal perfect hash。
//   - 如果 key 数量巨大，穷举 seed 的做法不一定高效，例子仅说明原理。
func BuildPerfectHash(keys []string) (hashes []uint64, iter int) {if len(keys) == 0 {return nil, 0}// 从 seed = 1 开始一轮一轮尝试for seed := uint64(1); ; seed++ {iter++seen := make(map[uint64]int, len(keys))hashes = make([]uint64, len(keys))collision := falsefor i, k := range keys {h := hashStringWithSeed(k, seed)if prevIdx, ok := seen[h]; ok {// 发现碰撞，当前 seed 失败，换下一轮_ = prevIdx // 这里你也可以记录一下是哪个 key 冲突collision = truebreak}seen[h] = ihashes[i] = h}if !collision {// 当前 seed 对所有 key 都无碰撞，认为构造成功return hashes, iter}// 否则继续下一轮 seed++}
}func main() {keys := []string{"GET /health","POST /login","POST /logout","GET /user","PUT /user",}hashes, iter := BuildPerfectHash(keys)fmt.Printf("构造成功，使用的迭代轮次 n = %d\n", iter)for i, k := range keys {fmt.Printf("key[%d] = %-15q  hash = %d (0x%x)\n",i, k, hashes[i], hashes[i])}
}