求适配64位键的Python最小完美哈希库：可输出参数用于C移植

针对你的需求，我有几个实用的方案来解决64位键转16位最小完美哈希的问题，同时搞定负索引和C语言移植的痛点：

既然perfection库对64位键支持不佳，试试这些替代方案：

• pyperfect：这个库专门用于生成最小完美哈希，原生支持64位整数键，并且可以输出哈希函数的核心参数（比如双哈希机制所需的两个哈希函数系数），方便你直接把逻辑移植到C语言。使用时只需传入你的键集，它会生成对应的映射规则，同时输出可复用的参数。
• 自定义实现Steve Hanov算法：既然你已经研究过这个算法，只需要调整哈希输出的处理逻辑就能解决负索引问题，完全不需要依赖第三方库，灵活性拉满。

你遇到的负索引本质是Python整数是有符号类型，哈希计算结果可能超出16位有符号整数的范围。解决起来非常简单：

• 在Python中，计算完哈希值后执行hash_value & 0xFFFF，就能把任何整数（包括负数）转换为0-65535之间的无符号16位整数。比如-123 & 0xFFFF会得到65413，完全符合你的索引需求。
• 移植到C语言时，只需要把哈希结果强制转换为uint16_t类型，C的无符号类型会自动处理符号位，不需要额外的判断逻辑，完美省去那4个周期的开销。

假设你用FNV-1a 64位哈希结合双哈希法实现完美哈希，C端的代码示例大概是这样：

1. 先在Python中确定双哈希的关键参数（比如两个哈希函数的系数），确保所有键都能映射到唯一的16位索引。
2. 在C中实现和Python完全一致的哈希函数：

#include <stdint.h>

// FNV-1a 64位哈希函数，和Python中的实现保持完全一致
uint64_t fnv1a_64(uint64_t key) {
    const uint64_t FNV_OFFSET = 14695981039346656037ULL;
    const uint64_t FNV_PRIME = 1099511628211ULL;
    uint64_t hash = FNV_OFFSET;
    uint8_t* bytes = (uint8_t*)&key;
    for (int i = 0; i < 8; i++) {
        hash ^= bytes[i];
        hash *= FNV_PRIME;
    }
    return hash;
}

// 完美哈希计算函数，参数从Python生成的结果中获取
uint16_t perfect_hash(uint64_t key) {
    uint64_t h1 = fnv1a_64(key);
    // 示例h2哈希函数，实际参数从Python生成的完美哈希规则中获取
    uint64_t h2 = (key * 0xDEADBEEFCAFEBABEULL) >> 48;
    // 计算索引并转成无符号16位
    return (uint16_t)((h1 + h2) % 0x10000);
}

3. 把Python生成的索引-值映射表转换成C数组，通过perfect_hash计算的索引直接访问数组即可。

如果你不局限于Python库，gperf是个非常成熟的工具——它可以读取你的键集文件，直接生成纯C的完美哈希函数代码，完全不需要外部依赖，生成的代码效率极高，非常适配你的C端应用场景。

内容的提问来源于stack exchange，提问作者Siddharth Chabra