algorithm - 什么是好的哈希函数？

Question

什么是好的哈希函数？我在大学的数据结构类(class)中看到了很多散列函数和应用程序，但我主要了解到要制作一个好的散列函数非常困难。作为避免碰撞的经验法则，我的教授说:

function Hash(key)
  return key mod PrimeNumber
end

(mod 是 C 和类似语言中的 % 运算符)

用质数作为哈希表的大小。我知道这是一个很好的避免碰撞的功能，而且速度很快，但是我怎样才能做出更好的呢？是否有针对数字键的字符串键更好的哈希函数？

Answer 1

通用哈希没有“好的哈希函数”之类的东西(编辑。是的，我知道有“通用哈希”之类的东西，但这不是我的意思)。根据上下文不同的标准确定散列的质量。已经有两个人提到了 SHA。这是一个加密散列，它对您可能指的散列表一点用处都没有。

哈希表有非常不同的要求。但是，要找到一个通用的好散列函数仍然很困难，因为不同的数据类型会公开不同的可以散列的信息。根据经验，最好平等地考虑一个类型拥有的所有信息。这并不总是容易的，甚至是不可能的。出于统计(以及因此碰撞)的原因，在问题空间(即所有可能的对象)上生成良好的分布也很重要。这意味着当散列 100 到 1050 之间的数字时，让最高有效数字在散列中扮演重要角色是不好的，因为对于大约 90% 的对象，这个数字将是 0。让最后三个重要得多数字决定哈希值。

同样，在对字符串进行哈希处理时，重要的是要考虑所有字符——除非事先知道所有字符串的前三个字符都相同；考虑这些那就是一种浪费。

这实际上是我建议阅读 Knuth 在 The Art of Computer Programming, vol. 中所说内容的情况之一。 3. 另一本好书是 Julienne Walker 的 The Art of Hashing .