algorithm - 寻找中等强度的哈希函数

Question

我有一组静态的 ~35000 个唯一 ASCII 文本字符串，每个字符串从 20 到 60 个字节不等。我想在其中引入一个唯一索引。出于各种原因，简单地编号是不可取的。

像 MD5 这样的加密级函数工作得很好，但我觉得这些有点矫枉过正。这最终是针对移动项目的，所以我对存储和 CPU 周期都比较贪心。另一方面，我尝试了 32 位 Adler32 并遇到了冲突。

谁能想出一个生成 64 位值的好散列函数？

Answer 1

因为你拥有的字符串集是固定的，你应该尝试寻找一个 perfect hash function ，一种专门针对一组数据设计的哈希函数，以保证不会发生冲突。有很多工具可以创建这样的哈希函数，其中之一， gperf (不要与 gprof 混淆)我知道是免费提供的。我强烈建议这样做。

如果您以后最终需要更改字符串集并想要一个轻量级、简单的哈希函数，您可能需要考虑使用 Rabin-Karp rolling hash function 。可以使用 O(n) 次加法、乘法和取模对长度为 n 的字符串进行计算，并确保每两个字符串都具有成对独立的哈希值。此外，您可能可以在大约半小时内编写代码，以测试它的性能是否优于阿德勒校验和。

也就是说，如果您不想实现加密安全，那么使用像 MD5 这样的知名散列函数可能仍然是一个好主意。在这种情况下，即使是简单的 CRC32 也可能就足够了。