针对字符串的哈希冲突和性能，最佳哈希算法是什么？

Question

针对字符串的哈希冲突和性能，最佳哈希算法是什么？

c#algorithmhash

54

如果我们有以下优先级（按照顺序），哪种哈希算法是最好的：

最小化哈希冲突
性能

它不一定要安全。基本上，我正在尝试创建一个基于某些对象的属性组合的索引。所有属性都是字符串。

如果有任何关于C#实现的参考资料，将不胜感激。

- dimitrisp

22

以下页面包含多种通用哈希函数的实现，它们高效且具有最小的冲突：http://partow.net/programming/hashfunctions/index.html - Matthieu N.

@Matthieu N 你是如何每次发布这个帖子都能获得恰好15个赞的？ - nawfal

@dimitrisp 你说得对。让我投票重新开放这个问题。但是吸引我的是看到很多类似的相关问题。关于这个https://dev59.com/RXVD5IYBdhLWcg3wBm1g，虽然它是一个C++问题，但怎么样？ - nawfal

请务必指定一个哈希函数，将等效的“属性”集合映射到相同的值。（您的“属性”可能有一些应该被忽略的东西，例如序列，多重性或大小写。在颜色与色调之间没有更好的选择……） - greybeard

我推荐使用BCrypt。虽然它不是最好的，但在安全性和实现的便捷性之间取得了很好的平衡。我在这里写了一篇文章：http://davismj.me/blog/bcrypt/ - Matthew James Davis

显示剩余3条评论

9个回答

17

正如Nigel Campbell所指出的那样，没有所谓的“最佳”哈希函数，因为它取决于你要哈希的数据特征以及是否需要具有密码质量的哈希。

话虽如此，以下是一些提示：

由于输入哈希的项只是一组字符串，您可以简单地合并每个单独字符串的哈希码。我见过以下伪代码的建议来执行此操作，但我不知道任何特定的分析：

int hashCode = 0;

foreach (string s in propertiesToHash) {
    hashCode = 31*hashCode + s.GetHashCode();
}

根据这篇文章，System.Web有一个内部方法，可以使用哈希码进行组合。

combinedHash = ((combinedHash << 5) + combinedHash) ^ nextObj.GetHashCode();

我也看到过一些简单地使用异或操作合并哈希码的代码，但我认为这是一个糟糕的想法（虽然我没有分析来支持这个观点）。如果同样的字符串以不同的顺序被哈希，则最终会产生冲突。

我已经成功地使用了FNV哈希函数：http://www.isthe.com/chongo/tech/comp/fnv/

Paul Hsieh有一篇不错的文章：http://www.azillionmonkeys.com/qed/hash.html

Bob Jenkins还写了一篇不错的文章，最初发表在1997年的Doctor Dobb's Journal上（链接中的文章进行了更新）：http://burtleburtle.net/bob/hash/doobs.html

- Mike B

3

MurmurHash2非常快速且分布良好。http://murmurhash.googlepages.com/ - Steven Sudit

8

没有一个单一的最佳哈希算法。如果您有已知的输入域，可以使用完美哈希生成器（例如gperf）生成一个哈希算法，该算法将在该特定输入集上获得100％的成功率。否则，对于这个问题，没有一个“正确”的答案。

- Nigel Campbell

不是的，但也有一些错误的。有些哈希函数在分布方面表现得很差，更不用说执行时间了。 - Steven Sudit

8

我这里的回答可能更偏向理论，而不是针对性的答案，但请从中获取价值。

首先，有两个明显的问题：

a. 碰撞概率 b. 哈希性能（即时间、CPU周期等）

这两个问题之间存在轻微的相关性，但并非完全相关。

问题a涉及到哈希后的结果空间与原始数据空间之间的差异。当你对一个1KB（1024字节）的文件进行哈希，得到32字节的哈希值时，会有：

1,0907481356194159294629842447338e+2466（一个有2466个零的数字）种输入文件的可能组合

哈希空间将有

1,1579208923731619542357098500869e+77（一个有77个零的数字）

它们之间的差距非常大，相差2389个零。由于我们将10^2466个情况缩减为10^77个情况，因此一定会发生碰撞（碰撞是指两个不同的输入文件具有完全相同的哈希值）。

唯一减少碰撞风险的方法是扩大哈希空间，从而使哈希值更长。理想情况下，哈希值应该与文件长度相同，但这有点蠢。

第二个问题是性能。这仅涉及哈希算法。当然，更长的哈希值很可能需要更多的CPU周期，但更智能的算法可能不需要。对于这个问题，我没有明确的答案。这太难了。

但是，你可以对不同的哈希实现进行基准测试/测量，并从中得出预先结论。

祝你好运;)

- Andrei Rinea

3

Java的String类使用的简单hashCode可能展示了一个适合的算法。

下面是"GNU Classpath"的实现。(许可证：GPL)

  /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

- David

2

您可以使用Knuth哈希函数（在此处描述）来同时获取两者。

假设哈希表大小为2的幂，这个函数非常快速——只需一个乘法、一个移位和一个按位与操作。更重要的是（对于您而言），它非常擅长最小化碰撞（请参见此分析）。

一些其他好的算法在此处被描述。

- Jason Cohen

1

他正在对字符串进行哈希，而不是整数。 - Nick Johnson

1

这是一个实现自己的直接方法: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html 以下是文章中的一段摘录:

例如，如果我们有一个由大写英文字母组成的字符集，那么字符集的长度为26，其中A可以用数字0表示，B可以用数字1表示，C可以用数字2表示，以此类推，直到Z用数字25表示。现在，每当我们想将该字符集的字符串映射到唯一的数字时，我们执行与二进制格式相同的转换。

- Abhishek Jain

是的，那样做可以实现，但需要很大的计算能力。 - TMS

1

这里是布谷鸟哈希。

查找只需要检查哈希表中的两个位置，在最坏情况下需要常数时间（参见大O符号）。这与许多其他哈希表算法不同，后者可能没有在查找时具有恒定的最坏情况时间界限。

我认为这符合您关于冲突和性能的标准。看起来这种类型的哈希表只能达到49%的填充率。

- Jason Z

5

这是在计算哈希值之后用于散列表本身的算法。问题在于如何计算一个好的哈希值。 - Jon Skeet

7

Jon Skeet 已经发言了。你失败了。:P - Andrei Rînea

1

"Murmurhash"在性能和冲突方面都表现不错。在提到的"softwareengineering.stackexchange"线程中进行了一些测试，Murmur获胜。我编写了自己的C#端口MurmurHash 2到.NET，并在一个包含466k个英文单词的列表上进行了测试，得到了22个冲突。结果和实现在这里：https://github.com/jitbit/MurmurHash.net（免责声明，我参与了这个开源项目！）

- Alex from Jitbit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mecki · Accepted Answer

忘掉"最好"这个词。无论任何人想出什么哈希算法，除非你有一个非常有限的数据集需要被哈希，否则每个平均性能表现出色的算法都可能在只输入正确（或从您的角度来看是“错误”）的数据时变得完全无用。

与其浪费太多时间考虑如何使哈希更加碰撞自由而不使用太多CPU时间，我宁愿开始思考“如何使碰撞问题不那么棘手”。例如，如果每个哈希桶实际上是一个表格，并且所有在此表格中发生冲突的字符串都按字母顺序排序，则可以使用二分查找（仅为O（log n））在桶表中进行搜索。这意味着，即使每秒哈希桶有4个碰撞，您的代码仍将具有良好的性能（与无碰撞表格相比会稍慢一些，但不会太慢）。这里的一个很大的优点是，如果您的表足够大并且您的哈希不太简单，则导致相同哈希值的两个字符串通常看起来完全不同（因此二分搜索平均只需比较一或两个字符即可停止比较字符串；使每次比较非常快）。

实际上，我之前遇到过一种情况，直接在排序后的表格中使用二分搜索进行搜索比哈希更快！尽管我的哈希算法很简单，但要将这些值哈希需要相当长的时间。性能测试表明，只有当我有超过大约700-800个条目时，哈希才比二分搜索快。但是，由于该表永远不会变得大于256个条目，并且平均表格低于10个条目，基准测试清楚地表明，在每个系统和每个CPU上，二分搜索都更快。在这里，通常已经比较数据的第一个字节就足以导致下一个二分搜索迭代（因为第一或两个字节中使用的数据已经非常不同），这被证明是一个很大的优势。

因此，总结一下：我会选择一个不会在平均情况下引起太多碰撞且速度较快的良好哈希算法（即使出现一些更多的碰撞，只要速度很快也可以接受！），并尽可能地优化我的代码，以便在出现碰撞时获得最小的性能损失（而且它们肯定会发生！除非您的哈希空间至少与您的数据空间一样大或更大，并且您可以将唯一的哈希值映射到每个可能的数据集）。