7

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

int bucket_for_s = h(s) % 10

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

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

或者，有没有一个进程可以生成一系列h2()，h3()...这样1：每个hash函数都比前一个好2：我只需要生成合理数量的hash功能？

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

4

4 回答 4

7

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

如果您使用的是 Java 之类的东西hashCode()，我认为它看起来像

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

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

尝试使用 SHA-256 等加密哈希作为基础。

Google 的City Hash的分布不如SHA-256好，但速度要快得多。这可以以更少的计算成本提供足够的分布。

于 2012-08-24T00:28:59.787 回答
6

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

可能的候选人

根据您的描述，散列函数应该是确定性的（您的“hello”示例） - 这适用于所有散列函数 - 并且应该生成均匀分布。

像SHA-256这样的加密散列应该满足您的要求，因为它输出完全不同的散列，即使对于像“hello”和“hallo”这样略有不同的输入也是如此。通过对哈希使用模 (%) 操作，您可以拥有任意数量的存储桶（当然不超过哈希的数量）。

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

您可能更愿意寻找所谓的“非加密哈希函数”，它们具有宽松的属性并且更适合查找 - 因此它们针对速度进行了优化。Java 的hashCode()、MurmurHash和已经提到的 CityHash（Google 公告）可能是一个好的开始。

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

也就是说，由于散列函数对于输入是确定性的，因此某个输入作为“hello”的散列将始终相同，即使您多次调用散列函数也是如此。如果您的数据集包含一些具有大量精确重复的元素（例如，“a”和“the”通常是标记化文本的嫌疑人），那么无论您使用哪种哈希函数，这很容易导致存储桶大小不均匀。

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

于 2012-08-24T14:20:13.723 回答
0

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

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

h2()现在，目标是使用以下参数找到这样的分布p1, q1, p2, q2：给定存储桶 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

p1,q1,p2,q2这是具有 4 个变量（分布参数）的 4 个方程的线性系统h2()。

注意：如果有 10 个桶，我们将h()拥有p1, p2, ..., p10where p1 + p2 + ... + p10 = 1。如果桶数> 2，则方程式少于未知数：对于每个分配，就像p1您获得h2()with的一个组件一样p11+p12+...+p1_10=1。因此，对于 10 个桶，有 100 个未知参数h2()和只有 20 个方程。这意味着h2()在求解剩余参数的方程之前，可以为 80 个参数赋予一些任意（但可行的）值。不漂亮，但仍然是一个解决方案。

于 2012-08-24T12:53:22.627 回答
0

哈希函数旨在产生均匀分布。如果您的数据不是这种情况，那么您的数据在某种程度上是该特定哈希函数的“部分”逆，当您选择其他数据时问题应该会消失。

鉴于这是一个理论问题，一种方法是：

美白彩色噪声

你可以玩int bucket_for_s

int bucket_for_s = put_in_bucket(s)

put_in_bucket:
    x = h(s) % 10 + 10*((h(s)/10)%10)
    if(0<=x<=2) return 0
    if(3<=x<=5) return 1
    if(6<=x<=9) return 2
    #The previous bucket_1 (30%) is now split into 3 buckets
    if(10<=x<=27) return 0
    #The previous bucket_2 (5%) is now enlarged
    #to incorporate more of the small old buckets (or parts of buckets)
    #This bucket is now bucket_4
    #... more of the same 
    if(83<=x<=99) return 9

您可以将这个想法扩展另一个数字，直到您对“解决方案”感到满意为止

您可以从中取出逻辑put_in_bucket并将其投入h2(s)使用h1(s)。

这种方法用于为白噪声着色（或在本例中为白噪声），因此得名。

于 2016-04-18T12:00:24.283 回答