c - 已知值的完美哈希

Question

假设我有一些已知值，我想根据这些值创建一个哈希表。例如，

For 0x78409 -> 1
For 0x89934 -> 2
For 0x89834 -> 3

等...

但这些值(0x78409、0x89934、0x89834)仅在运行时已知，因此不能使用switch/case。然而，它们在执行开始时就已知了，所以也许我们可以创建一个哈希函数，它可以 self 调整以制作一个完美的哈希表。所以我的问题是，我们能否为这种情况创建一个完美的哈希函数。

Answer 1

如果在创建 hashmap 之前知道整个输入域，那么这是可能的，但需要某种形式的运行时代码生成，通过 VM 或 JIT(可能通过脚本语言，如 LuaJIT)，即将允许您使用 gperf及其同类产品在运行时创建哈希，编译它，然后使用它来填充和从 map 中检索。

一个更简单、更可行的解决方案是对给定的一组输入排列使用具有极低冲突的哈希函数(例如:您可能只使用字母、小写字符)，一个最小的完美哈希。

Murmur3 和 crapwow 是需要注意的(尽管我对 crapwow 持谨慎态度)，Google's CityHash , 和 xxHash也值得一看。 Bob Jenkins 也有一个很好的基于最小完美散列的 map 可用 here ，这也应该做得很好。