perfect-hash - 最小完美散列函数

Question

我在 [0; 范围内有很多整数；2^63-1]。然而，只有 10^8 个整数。没有重复。完整列表在编译时是已知的，但它只是唯一的随机数。这些数字永远不会改变。要显式
存储一个整数，需要 8 个字节，并且有关联的 1 个字节值，因此显式存储需要大约 860 MB。 所以我想找到最小的完美散列函数来将 10^8 个整数中的每一个从 [0;2^63-1] 映射到 [0;10^8-1]。我应该只找到这个函数一次，数据永远不会改变，函数可能很复杂。但它应该是最小的、完美的，并且计算应该很快。我怎样才能更好地做到这一点？如果它们发生，也许可以找到并使用一些子序列？

谢谢。

Answer 1

让您的计算机为您完成工作：

http://www.gnu.org/software/gperf/

引用：“GNU gperf 是一个完美的哈希函数生成器。对于给定的字符串列表，它以 C 或 C++ 代码的形式生成哈希函数和哈希表，用于根据输入字符串查找值。哈希函数是完美的，这意味着哈希表没有冲突，哈希表查找只需要单个字符串比较。”

Answer 2

我正在研究每个密钥需要少于 1.6 位的算法和 Java 实现。

以前，我用 Java 实现了一个最小的完美散列函数工具，每个键需要少于 2.0 位。

其他算法在CMPH中实现。例如，默认情况下，CHD 每个密钥需要大约 2.06 位。它可以配置为使用更少的空间，但生成速度会变慢。