什么是好的哈希函数？

Question

什么是良好的哈希函数？我在大学的数据结构课程中看到了很多哈希函数和应用程序，但是我大多数都知道要创建一个好的哈希函数非常困难。为了避免发生冲突，我的教授说：

function Hash(key)

  return key mod PrimeNumber

end

（mod是C和类似语言的％运算符）

质数应为哈希表的大小。我知道这是一个不错的功能，可以避免碰撞，而又可以避免快速碰撞，但是我怎样才能制造出更好的呢？是否有针对数字键的字符串键更好的哈希函数？

Answer 1

没有通用哈希的“良好哈希函数”之类的东西（是的，我知道有“通用哈希”之类的东西，但这不是我的意思）。取决于上下文，不同的标准确定哈希的质量。已经有两个人提到SHA。这是一个加密哈希，对于哈希表（您可能要说的）根本没有好处。哈希表有非常不同的要求。但是，仍然很难普遍地找到一个好的哈希函数，因为不同的数据类型会公开不同的可以哈希的信息。根据经验，最好将一种类型的所有信息均等地考虑在内。这并不总是那么容易甚至不可能。出于统计原因（并因此产生冲突），在问题空间（即所有可能的对象）上产生良好的分布也很重要。这意味着，当对100到1050之间的数字进行哈希处理时，让最高有效位在哈希表中扮演重要角色是不好的，因为对于90％的对象，该数字将为0。让最后三个数字更重要数字确定哈希。同样，在对字符串进行哈希处理时，考虑所有字符也很重要–除非事先知道所有字符串的前三个字符都相同，考虑这些便是浪费。实际上，这是我建议阅读Knuth在《计算机编程艺术》第一卷中说的内容之一。3.另一本好书是朱丽安·沃克（Julienne Walker）的《散列的艺术》。

Answer 2

哈希函数有两个主要目的：将数据点均匀分散到n位。安全地识别输入数据。不知道您要使用的哈希是不可能推荐哈希的。如果您只是在程序中创建哈希表，则无需担心该算法的可逆性或可破解性……SHA-1或AES对此完全没有必要，最好使用FNV的变体。FNV与您提到的简单质数调制相比，具有更好的分散性（从而减少了冲突），并且更适应于各种输入大小。如果您使用散列来隐藏和验证公共信息（例如对密码或文档进行哈希处理），则应使用由公众审查审查的主要哈希算法之一。哈希函数休息室是一个不错的起点。