改进散列函数值的分布

Question

假设我有非常多的字符串(比如100亿个字符串，每个字符串大约50个字符)。我想将字符串分配到恰好10个桶中。每个桶应该容纳大约10%的字符串。使用散列函数h()，我可以这样做：

int bucket_for_s = h(s) % 10

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

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

或者，有没有一个进程可以生成一系列散列函数h2()，h3()...因此，1:每个哈希函数都比前一个更好，2:我只需要生成合理数量的哈希函数？

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

Answer 1

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

如果您正在使用类似于Java的hashCode()的东西，我认为它类似于

s*31^(n-1) + s1*31^(n-2) + ... + sn-1

您可能会看到一个不太理想的散列分布。

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

与SHA-256相比，谷歌的City Hash分布不那么均匀，但速度要快得多。这可能会以较少的计算开销提供足够的分布。

Answer 2

链接散列函数或生成一系列散列函数在计算上是不必要的昂贵的。您应该使用已经具有开箱即用的所需属性的散列函数。

可能的候选者

根据您所描述的，哈希函数应该是确定性的(您的"hello“示例)-这对于所有哈希函数都是正确的-并且应该生成均匀分布。

像SHA-256这样的加密散列应该能满足您的需求，因为它输出的散列完全不同，即使是对于像"hello“和"hallo”这样的微小差异的输入也是如此。通过对散列使用模(%)运算，您可以拥有任意数量的存储桶(当然不超过散列的数量)。

然而，密码学哈希函数是为安全和校验而构建的，并且涉及一些复杂的计算。在您的情况下，您很可能不需要它们提供的强大的安全相关属性。

您可能更希望寻找所谓的“非加密散列函数”，这些散列函数具有宽松的属性，并且更多地是为查找而设计的-因此它们针对速度进行了优化。Java的hashCode()、MurmurHash和已经提到的CityHash (Google announcement)可能是一个很好的开始。

散列函数的确定性与散列的均匀分布

也就是说，由于哈希函数对于输入是确定性的，因此，即使您多次调用哈希函数，作为"hello“的特定输入的哈希也将始终相同。如果您的数据集包含一些具有大量精确重复项的元素(例如，"a“和"the”是标记化文本的常见疑点)，则无论您使用哪种哈希函数，都很容易导致存储桶大小不一致。

假设您想要使用散列的均匀分布来均匀分布工作负载，可以使用以下策略来克服这一点。可以将每个存储桶视为可由任何可用机器处理的工作包或作业。如果您的工作包比机器多(假设10台机器有20或30个包)，只要您允许灵活的调度，您就可以平均分配工作负载。当机器A获得其中一个超大包并花费一些时间进行处理时，机器B可以同时处理两个中小型包，从而降低了超大包对整体性能的影响。

Answer 3

关于如何解决它的方向简化为2个桶，而不是10个或N个。

假设您得到一个分布h()，其中分配给存储桶1的p和分配给存储桶2的q，当然还有p + q = 1。

现在，我们的目标是找到这样的具有参数p1, q1, p2, q2的分布h2()：给定存储桶1，它使用机会p1, q1 (p1+q1=1)，给定存储桶2，它使用机会p2, q2 (p2+q2=1)

         h()          h2()

                 / bucket1 p*p1 
      bucket1 p -
    /            \ bucket2 p*q1 
 x -
    \            / bucket1 q*p2 
      bucket2 q -
                 \ bucket2 q*q2 

我们的目标是使所有2个桶的机会相等：

p*q1 + q*p2 = 1/2  (total chances for bucket 1 after h2())
p*q2 + q*q2 = 1/2  (total chances for bucket 2 after h2())

和以前一样：

p1 + q1 = 1
p2 + q2 = 1

这是一个由4个变量(分布h2()的参数p1,q1,p2,q2 )的4个方程组成的线性系统。

注意:有了10个存储桶，我们就有了带有p1, p2, ..., p10 where p1 + p2 + ... + p10 = 1的h()。当存储桶的数量大于2时，方程的数量要比未知数少:对于每个分配，比如p1，你会得到一个带有p11+p12+...+p1_10=1的h2()组件)。因此，对于10个桶，有100个未知参数的h2()和只有20个方程。这意味着在求解剩余参数的方程之前，可以为h2()的80个参数指定一些任意值(但可行)。不是很漂亮，但仍然是一个解决方案。