c - 在这种情况下是否可以制作一个最小的完美哈希函数？

Question

我想创建一个 HashMap (或其他结构，如果您有任何建议)来存储键值对。键将在创建 map 的同时立即插入，但我不知道键是什么(任意长度的字符串)，直到运行时，当我需要创建 map 时。

我正在解析这样的查询字符串 "x=100&name=bob&color=red&y=150"(但该字符串可以有无限数量的变量，并且变量可以有任意长度的名称)。

我想解析一次并创建一个Hash Map，最好是最小的并且具有完美的哈希函数以满足线性存储要求。创建 map 后，不会修改或删除值，也不会向 map 添加更多键值对，因此整个 map 实际上是一个常量。我假设变量不会在字符串中出现两次(IE。"x=1&x=2" 无效)。

我在 C 中编码，目前有一个函数可以使用，例如 get("x")，它将返回字符串 "100"，但它每次都解析查询字符串，这需要 O(n) 时间。我想在第一次加载时解析一次，因为它是一个非常大的查询字符串，每个值都会被读取多次。即使我使用的是 C，我也不需要 C 中的代码作为答案。伪代码或任何建议都很棒!

Answer 1

试试 GPL 的 gperf , 或 Bob Jenkins' public domain implementation in C

过程:

• 接收查询字符串并通过枚举键列表识别完美哈希函数的域

• 将这些键和列表大小(范围将为 1..size)提供给从上述引用实现派生的完美哈希生成函数

• 使用生成的完美哈希函数创建HashMap

• 使用相同的完美哈希函数处理HashMap中的get请求

编辑 Necrolis 在下面的评论中指出，引用实现在 C 源代码中输出完美的哈希函数，因此您需要修改它们以生成类似于 VM 的字节码之类的东西。您还可以使用解释性语言，例如嵌入式 Scheme 或 Lua。

当创建完美哈希函数的开销在查找中分摊时，知道这是否值得为简单(非完美)HashMap 付出努力会很有趣

另一个选项是 Cuckoo hashing它也有 O(1) 查找