一个好的哈希函数是什么？

Question

什么是好的哈希函数？在我的大学数据结构课程中，我看到了许多哈希函数和应用程序，但基本上我得出的结论是很难编写一个好的哈希函数。作为一个避免冲突的经验法则，我的教授说：

function Hash(key)
  return key mod PrimeNumber
end

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

使用质数作为哈希表的大小。 我知道这是一种避免冲突和快速的好方法，但我怎样才能做得更好呢？ 是否有更好的字符串键和数字键的哈希函数？

- Hoffmann

---

你是否考虑过使用以下通用哈希函数之一或多个：http://www.partow.net/programming/hashfunctions/index.html - Matthieu N.

在 fnv_func 中，p[i] 的类型是 char，第一次迭代后 h 会发生什么？ 这是有意为之的吗？ - user921223

@martinatime说：“维基百科上有很多关于哈希函数的信息http://en.wikipedia.org/wiki/Hash_function，而这篇文章http://www.partow.net/programming/hashfunctions/index.html的底部则提供了各种语言实现的算法。” - 2501

Answer 1

对于通用哈希函数而言，并不存在所谓的“好的哈希函数”（注：我知道有“通用哈希”的概念，但那不是我想说的）。因为在不同的情况下，不同的标准决定了哈希的质量。两个人已经提到了SHA。它是一种加密哈希，但对于你可能想要的哈希表来说并不好。

哈希表具有非常不同的要求。但是，由于不同的数据类型公开了可以哈希的不同信息，因此普遍找到一个好的哈希函数很困难。作为经验法则，最好平等地考虑一个类型持有的所有信息。这并不总是容易甚至可能不可能。出于统计学原因（因此发生冲突），生成问题空间（即所有可能的对象）上的良好散布也很重要。这意味着当哈希数字介于100和1050之间时，让最高位数字在哈希中占主导地位并不好，因为对于约90％的对象，该数字将为0。让最后三个数字确定哈希值更加重要。

同样，在哈希字符串时，重要的是考虑所有字符 - 除非预先知道所有字符串的前三个字符都相同;在这种情况下，考虑这些字符是浪费的。

实际上，这是我建议阅读Knuth在《计算机程序设计艺术》第3卷中所说的内容之一。另一个好的读物是Julienne Walker的哈希的艺术。

- Konrad Rudolph

---

Konrad，从理论角度来看，你肯定是正确的，但你有没有尝试过我在评论中提到的Paul Hsieh哈希函数？它对许多不同类型的数据确实非常有效！ - Chris Harris

“通用哈希函数”并不存在所谓的“好的哈希函数”（注：是的，我知道有“通用哈希”这个概念，但那不是我想说的）。“通用哈希”和“通用哈希函数”在意义上有什么区别？ - Honinbo Shusaku

@Abdul，没有这样的事情。我在写这个答案时所选用的措辞非常糟糕。我的意思是，通用哈希函数只能对预期情况即平均行为进行保证，而不能对最坏情况进行保证。但实际上，通用哈希比我的答案听起来要好得多。老实说，整个答案都不太好，今天我也不会像当初那样写初始段落。 - Konrad Rudolph

链接 https://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx 已失效。 - Joseph Quinsey

Answer 2

对于基本上任何类型的数据，如果需要进行“普通”哈希表查找，Paul Hsieh 的这个哈希函数是我用过的最好的一个。

http://www.azillionmonkeys.com/qed/hash.html

如果您关心密码安全或其他更高级的内容，则可能因人而异。 如果您只想要一个绝佳的通用哈希函数用于哈希表查找，那么这就是您要寻找的东西。

- Chris Harris

---

我曾经从Jenkins的网站上读到，SFH是最好的之一，但我认为Murmur可能会更好，可以看看这个优秀的答案：http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633 - nawfal

谢赫的哈希函数很糟糕，碰撞比我们想要的多一个数量级。特别是，仅在最后4个字节不同的字符串很容易发生碰撞。如果您有一个30个字符的字符串，在处理了28个字节之后，哈希值仅在最后2个字节中不同。这意味着您保证会在剩下的两个字节值中发生碰撞。（是的，它很快。那又怎样。） - Andrew Lazarus

Answer 3

哈希函数有两个主要目的：

• 将数据点均匀地散布到n位中。
• 安全地识别输入数据。

不知道您使用哈希函数的具体用途，因此无法推荐特定的哈希函数。

如果您只是在程序中创建哈希表，那么您无需担心算法的可逆性或易受攻击性...对于此问题，SHA-1或AES完全不必要，您最好使用FNV变体。 FNV实现了比您提到的简单质数模更好的散布效果（从而减少冲突），并且它更适应各种输入大小。

如果您正在使用哈希函数隐藏和验证公共信息（例如哈希密码或文档），那么您应该使用经过公众审核的主要哈希算法之一。 哈希函数休息室 是一个很好的起点。

- Myrddin Emrys

---

更新哈希函数休息室链接：http://www.larc.usp.br/~pbarreto/hflounge.html - Tim Partridge

FNV相对于SHA1，在生日碰撞方面表现如何？例如，与SHA1中相同数量的位相比，FNV能承受多少生日碰撞？ - Kevin Hsu

@Kevin 只要哈希的雪崩特性良好（输入微小变化=输出大幅变化），那么生日碰撞只是哈希位数的函数。在这方面，FNV-1a非常出色，您可以拥有任意多或少的哈希位数（尽管需要额外努力才能获得不是2的幂次方的位数）。 - Myrddin Emrys

Answer 4

这是一个好的例子，也是为什么你永远不想写一个的例子。它是一个Fowler / Noll / Vo（FNV）哈希，既包含计算机科学的天才又包含纯粹的巫术。

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

编辑：

• Landon Curt Noll 在他的网站上推荐使用 FVN-1A 算法代替原始的 FVN-1 算法：改进的算法更好地分散了哈希中的最后一个字节。我相应地调整了算法。

- Nick

---

请参考这个网站，了解为什么选择这些值：http://isthe.com/chongo/tech/comp/fnv/#fnv-prime - Cthutu

Answer 5

我认为最重要的原则是不要自己开发。尽量使用经过彻底测试的东西，例如SHA-1或类似的东西。

- Einar

---

他似乎不需要任何加密安全性，因此SHA-1会过于复杂。 - Nova

顺便提一下，尽管目前还没有发现SHA-1的碰撞，但人们认为在未来几年或几个月内会发现。我建议使用SHA-256。 - Samuel Allan

SHA-1现在已经不安全了。请使用SHA-3或SHA-2代替。SHA-3和SHA-2的链接分别为：https://fe-tool.com/en-us/hash/sha3 和 https://fe-tool.com/en-us/hash/sha256/。 - cwtuan

Answer 6

你的意思是想使用具有碰撞抗性的哈希函数，尝试使用SHA-2。或者尝试在单向压缩函数中使用（好的）分块密码（以前从未尝试过），例如Miyaguchi-Preenel模式中的AES。但问题是你需要：

1）拥有一个IV。尝试使用Khinchin常数的前256位小数部分之类的东西。 2）拥有填充方案。很容易。从像MD5或SHA-3（Keccak [发音为'ket-chak']）这样的哈希中借鉴它。 如果你不关心安全性（其他人也说过这个），可以看看FNV或Bob Jenkins的lookup2（实际上我是第一个推荐lookup2的人）。还可以尝试MurmurHash，速度很快（检查一下：.16 cpb）。

- Gavriel Feria

Answer 7

一个好的哈希函数具有以下特性：

1. 给定一条消息的哈希值，对于攻击者来说，计算找到另一条消息使它们的哈希值相同是计算上不可行的。

2. 给定一对消息m'和m，计算找到两个消息使得h(m)=h(m')是计算上不可行的。

这两种情况不是一样的。在第一种情况下，存在一个预先存在的哈希值，你正在尝试找到一个碰撞。而在第二种情况下，你正在尝试找到任意两条碰撞的消息。由于生日“悖论”，第二个任务要简单得多。

当性能不是重要问题时，你应该始终使用安全的哈希函数。攻击者可以通过强制哈希碰撞来进行非常巧妙的攻击。如果你一开始就使用了强大的哈希函数，你将保护自己免受这些攻击。

在新设计中不要使用MD5或SHA-1。大多数密码学家，包括我在内，都认为它们已经被破解了。这两种设计的主要弱点是第二个属性，即我上面概述的属性，在这些构造中不成立。如果攻击者可以生成两个消息m和m'，它们都散列到相同的值，他们可以利用这些消息来攻击你。如果您不小心，SHA-1和MD5也会受到消息扩展攻击，这可能会严重削弱您的应用程序。

像Whirpool这样更现代的哈希算法是更好的选择。它不会受到这些消息扩展攻击的影响，并使用与AES相同的数学方法来证明针对各种攻击的安全性。

希望这有所帮助！

- Simon Johnson

---

我认为在这种情况下推荐使用加密哈希函数是一个非常糟糕的建议。 - Slava

@Slava：为什么？你为什么说“在这种情况下使用加密哈希函数是一个非常糟糕的建议”？为什么这是个坏建议？有哪些相对劣势使它如此？ - Let Me Tink About It

因为哈希映射中使用的哈希函数应该快速且轻量级（假设它仍然提供良好的哈希），而加密哈希则特意被设计成计算成本高昂以防止暴力攻击。 - Slava

Answer 8

一个好的哈希函数应该

1. 当可能时具有双射性，以避免丢失信息，并且具有最少的碰撞
2. 尽可能均匀地级联，即每个输入位应该以0.5的概率且没有明显的模式翻转每个输出位。
3. 如果在密码上下文中使用，则不应存在有效地反演它的方法。

质数模数不满足这些要点。它只是不够好。它往往比什么都不做要好，但它甚至并不快速。使用无符号整数进行乘法并取2的幂模可以同样好地分配值，但是仅需要大约2个CPU周期，而质数模数需要15至40个周期（是的，整数除法确实如此缓慢）。

为了创建一个既快速又分布良好的哈希函数，最好的选择是从具有较低质量的快速排列组合而成，就像他们为随机数生成所做的PCG一样。

有用的排列包括：

• 奇数与乘法
• 二进制旋转
• xorshift

按照这个方法，我们可以创建自己的哈希函数或使用经过测试和广泛接受的splitmix。

如果需要加密质量，我强烈建议使用sha系列函数，这些函数经过了充分的测试和标准化，但出于教育目的，以下是如何创建一个：

首先，您需要选择一个良好的非加密哈希函数，然后应用一个单向函数，如素域上的指数运算或k次应用(n*(n+1)/2) mod 2^k，其中k是结果哈希中的位数，并在其中插入一个xorshift。

- Wolfgang Brehm

Answer 9

我强烈推荐 SMhasher GitHub 项目https://github.com/rurban/smhasher，它是一个用于测试哈希函数的测试套件。这里列出了最快的非加密哈希函数，而且没有已知的质量问题：https://github.com/rurban/smhasher#summary。

- otmar

Answer 10

不同的应用场景对哈希算法有不同的设计要求，但是一个好的哈希函数应该满足以下三点：

• 抗碰撞：尽量避免冲突。如果很难找到两个输入被散列到相同的输出，则哈希函数是防碰撞的。
• 防篡改：只要改变一个字节，其哈希值就会非常不同。
• 计算效率：哈希表是一种可以在时间消耗和空间消耗之间进行权衡的算法。

在2022年，我们可以选择SHA-2家族用于安全加密，SHA-3虽然更安全但性能损失更大。更安全的方法是添加盐并混合加密。

- cwtuan