1

在阅读 MSDN 上有关 Object.GetHashCode 方法的文档时，我遇到了诸如哈希函数之类的短语应该在哈希表中提供随机或有用的分布。这种分布对于散列函数或散列表意味着什么？

4

2 回答 2

13

散列函数产生一个 32 位整数，用于“平衡”散列表。假设您的表有一百个“桶”，并且您根据哈希函数的后两位十进制数字将表中的项目放入桶中。

现在假设散列函数总是产生 100 的偶数倍数。每个项目都将进入同一个桶，哈希表将不平衡。那将是一个糟糕的哈希函数。

无论您有多少个桶，也无论您如何从哈希中提取桶号，一个好的哈希算法都会产生大致均匀的分布。

于 2012-04-06T06:18:22.217 回答
2

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

最好的散列函数采用输入空间（Fred Astaire），并产生一个（理想情况下）输入空间唯一的随机值。只要散列的大小小于数据的大小，就无法完全避免冲突，但应通过仔细选择散列算法将其最小化。

正如下面 Eric 所指出的，平衡哈希表的哈希算法必须非常快，因此您必须在速度和冲突之间取得平衡。您可以研究像 SHA-1 (http://en.wikipedia.org/wiki/SHA-1) 这样的加密哈希算法来了解生成唯一哈希的复杂性，但是用于平衡哈希表的哈希算法需要尽可能快.

于 2012-04-06T06:20:34.753 回答