performance - 为数百万个项目创建完美的哈希 - 结果只需要“存在与否”

Question

有谁知道一个好的库（windows），它可以让我为数百万个项目（可能大约 10m）创建一个静态（而不是运行时）完美的散列？

我基本上有数百万组字符串，我想以最小的 O(1) 知道字符串是否在我的集合中 - 就是这样。我不需要它来实际查找字符串 - 它背后没有任何价值（除了存在之外）。

Answer 1

尝试：

• 鲍勃詹金斯的完美。
• CMPH
• gperf

perfect 和 gperf 以 C 代码形式生成表，在 Windows 上应该可以正常工作。我不知道 CMPH 的输出是什么。

CMPH 有评论说：

gperf 有点不同，因为它旨在为小密钥集创建非常快速的完美哈希函数，而 CMPH 库旨在为非常大的密钥集创建最小完美哈希函数。

如果这是正确的，那么对于您的百万密钥案例，您可能应该更喜欢 CMPH 而不是 gperf。我不知道他们与詹金斯的完美相比如何。尝试所有这三种方法并相互进行基准测试应该足够简单。

Answer 2

布隆过滤器可以满足您的需求，我会四处寻找拥有它们的库，或者您可以尝试自己编写一个。