改善散列函数值的分布

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"将转到bucket x,无论它存储在哪台机器上).

Answer 1

密码固体散列函数应该已经在散列输出的所有位上具有非常均匀的分布.

如果您使用的是类似hashCode()我认为的Java之类的东西

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

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

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

Google的City Hash分布不如SHA-256,但要快得多.这可以以较少的计算费用提供足够的分布.

Answer 2

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

可能的候选人

根据您的描述,哈希函数应该是确定性的(您的"问候"示例) - 对于所有哈希函数都是如此 - 并且应该生成均匀分布.

诸如SHA-256之类的加密哈希应该满足您的要求,因为它输出完全不同的哈希值,即使只是略微不同的输入,如"hello"和"hallo".通过对哈希使用模数(%)运算,您可以拥有任意数量的桶(当然不超过哈希的数量).

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

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

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

也就是说,由于散列函数对输入是确定性的,因此即使您多次调用散列函数,某个输入的散列"hello"也将始终相同.如果您的数据集包含一些具有大量精确重复的元素(例如"a"和"the"通常是令牌化文本的嫌疑人),则无论您使用哪种散列函数,这都很容易导致大小不均匀的存储桶.

假设您希望使用均匀分布的哈希来均匀分配工作负载,可以使用以下策略来克服这一点.将每个存储桶视为可由任何可用计算机处理的工作包或作业.如果您拥有的工作包多于计算机(例如,10台计算机可以使用20或30个包),只要您允许灵活的计划,就可以均匀地分配工作负载.当机器A获得一个超大型包装并需要一些时间来处理它时,机器B可以同时处理两个小型或中型包装,从而降低了超大型包装的整体性能影响.