hash - 改进哈希函数值的分布

Question

假设我有大量的字符串(比如 100 亿个字符串，每个字符串约 50 个字符)。我想将字符串分配到正好 10 个桶中。每个桶应该容纳大约 10% 的字符串。使用哈希函数 h() 我可以做到:

int bucket_for_s = h(s) % 10

然而，这不能保证分布的均匀性。假设我对所有字符串执行上述操作，并发现 30% 进入存储桶 1，5% 进入存储桶 2，依此类推。我的问题是:

给定 h() 分布，有没有办法生成一个新的散列函数 h2() 来更均匀地分布字符串？

或者，是否有一个过程可以生成一系列散列函数 h2(), h3()... 以便 1:每个散列函数都比前一个更好 2:我只需要生成合理数量的散列职能？

我还应该提到，不幸的是我不能简单地将输入分成 10 部分，因为我的输入分布在多台机器上。我正在寻找一个确定性的解决方案，我可以分别应用于每台机器并获得相同的结果(所以最终“你好”会转到存储桶 x，无论它存储在哪台机器上)。

Answer 1

加密可靠的散列函数应该已经在散列输出的所有位上具有非常均匀的分布。

如果您使用的是类似 Java 的 hashCode()我相信它看起来像

s[0]*31^(n-1) + s1*31^(n-2) + ... + s[n-1]

您很可能会看到不太理想的哈希分布。

尝试使用诸如 SHA-256 之类的加密哈希作为基础。

谷歌 City Hash分布不如 SHA-256 ，但要快得多。这可以以较少的计算开销提供足够的分布。