“散列函数的分布”是什么意思？

在阅读关于Object.GetHashCode方法的MSDN文档时，我遇到了类似于散列函数应该在散列表中提供随机或有用分布的短语。这个分布对散列函数或散列表意味着什么？“散列函数的分布”是什么意思？

来源

2012-04-06 surajnaik

http://en.wikipedia.org/wiki/Hash_table – 2012-04-06 06:12:37

粗略地说：散列值应该“在没有明显图案的情况下在其域内随机散布”（例如，当以可视方式查看时，最小结块和最大散布）。许多哈希实现将重新哈希散列，以减少在放入桶中时出现“出现”的可能性。 – 2012-04-06 06:15:31

为了“平衡”散列表，散列函数产生一个32位整数。假设你的表有一百个“桶”，并且你根据散列函数的底部两个十进制数字将表中的项放入一个桶中。

现在假设散列函数总是产生的数字甚至是偶数百的数字。每个项目将要进入同一个桶，并且哈希表将不平衡。这将是一个糟糕的散列函数。

好的哈希算法产生一个大致均匀分布无论你有多少个水桶有和无论你如何从哈希提取桶数。

来源

2012-04-06 06:18:22

为了使散列表的功能最大化，散列值应该尽可能唯一以防止冲突。例如，让我们考虑一个非常天真的散列函数：假设您的对象是名和姓，并且您的散列值可以选择首字母。所以Ginger Rodgers的哈希值是GR，而Fred Astaire的哈希值是FA。到目前为止这么好，但是当弗兰克艾伦配上FA的哈希值时会发生什么？现在你在Fred Astaire和Frank Allen之间发生冲突，并且散列表实现必须将其作为特殊情况处理，这会降低效率。

最好的散列函数需要输入空间（Fred Astaire），并产生一个随机值（理想情况下）是输入空间唯一的。只要散列的大小小于数据的大小，就没有办法完全避免冲突，但应该通过仔细选择散列算法来最小化它们。

正如Eric所指出的那样，为了平衡散列表，散列算法必须非常快速，所以你必须在速度和碰撞之间取得平衡。您可以学习像SHA-1（http://en.wikipedia.org/wiki/SHA-1）这样的加密哈希算法来理解生成唯一哈希的复杂性，但是用于平衡哈希表的哈希算法需要尽可能快。

来源

2012-04-06 06:20:34

直到最后一段，你都做得很好。加密散列函数的要求和散列函数对平衡散列表的要求是非常非常不同的，你不应该混淆这两者。你不应该使用像SHA1这样的算法来进行散列表平衡;请记住，散列表平衡算法的要点是*它是性能优化*，所以不要使用*慢且复杂的散列算法！ – 2012-04-06 06:40:50

好点，埃里克。我只是想指出一个散列算法，它在避免冲突方面做得非常好。我会相应地更新我的答案。 – 2012-04-06 06:42:35

有人可能会选择通过返回32位整数来散列32位整数。非常适合散列表平衡，对于加密散列很糟糕。为了理解散列表平衡散列函数，我建议不要研究加密散列算法。 – Brian 2012-04-09 15:36:55

“散列函数的分布”是什么意思？

回答

相关问题