在哈希冲突和字符串性能方面的最佳哈希算法

忘记“最好”这个词。无论任何人可能会想到哪种哈希算法,除非您有一组非常有限的数据需要进行哈希处理,否则平均而言性能非常好的每种算法都会变得完全无用,只要向正确的(或从您的角度来看是“错误的”)数据馈送数据。

我不想浪费太多的时间来思考如何在不使用太多CPU时间的情况下使哈希更无冲突,而是开始思考“如何减少冲突的问题”。例如,如果每个哈希桶实际上是一个表,并且此表中的所有字符串(发生冲突)都按字母顺序排序,则可以使用二进制搜索(仅为o(log n))在bucket表中搜索,这意味着,即使每秒钟哈希桶有4个冲突,您的代码仍将具有良好的性能(它的COM速度会稍慢一些)。削减到一个无碰撞的表,但没有那么多)。这里的一个很大的优点是,如果表足够大,哈希也不太简单,那么产生相同哈希值的两个字符串通常看起来完全不同(因此二进制搜索可以在平均一个或两个字符后停止比较字符串;使每次比较都非常快)。

事实上,我以前也遇到过这样一种情况:使用二进制搜索直接在已排序的表中搜索,结果发现比哈希更快!尽管我的哈希算法很简单,但是哈希值还是花了不少时间。性能测试表明,只有当我得到超过700-800个条目时,哈希搜索确实比二进制搜索快。然而,由于该表永远不会增长超过256个条目,并且由于平均表低于10个条目,基准测试清楚地表明,在每个系统、每个CPU上,二进制搜索速度更快。在这里,通常已经比较了数据的第一个字节的事实足以导致下一个bsearch迭代(因为数据在第一个字节到第二个字节已经非常不同了),这是一个很大的优势。

所以,总结一下:我会采用一个合适的哈希算法,它平均不会造成太多的冲突,而且速度相当快(如果只是非常快的话,我甚至会接受更多的冲突!)更确切地说,优化我的代码,一旦发生冲突,如何获得最小的性能损失(他们会的!除非散列空间至少等于或大于数据空间,并且您可以将唯一的散列值映射到每个可能的数据集。

AS Nigel Campbell 表示,没有“最佳”哈希函数,因为它取决于您要哈希的数据特征以及是否需要加密质量哈希。

也就是说,这里有一些要点:

• 由于用作哈希输入的项只是一组字符串,因此您可以简单地为每个单独的字符串组合哈希代码。我已经看到下面的伪代码建议这样做,但我不知道它的任何特定分析:

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

  根据 this article ,System.Web有一个内部方法,该方法使用

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

  我还看到了一些代码,它们只是XOR将哈希代码组合在一起,但这对我来说似乎是个坏主意(尽管我再次没有分析来支持这一点)。如果没有其他内容,那么如果相同的字符串按不同的顺序散列,则最终会发生冲突。

• 我使用了FNV,效果很好: http://www.isthe.com/chongo/tech/comp/fnv/

• 谢保罗有一篇很好的文章: http://www.azillionmonkeys.com/qed/hash.html

• Bob Jenkins的另一篇好文章,最初发表于1997年的Dobb博士期刊(链接文章有更新): http://burtleburtle.net/bob/hash/doobs.html

没有一个最佳哈希算法。如果你有一个已知的输入域,你可以使用一个完美的哈希生成器,比如 gperf 生成一个哈希算法,该算法将在特定的输入集上获得100%的速率。否则,这个问题就没有“正确”的答案。

我在这里将是跛脚的,给出一个更理论的回答,而不是一个针尖的答案,但请接受它的价值。

首先,有两个明显的问题:

A.碰撞概率 b.哈希性能(即:时间、CPU周期等)

这两个问题有点相互关联。它们并不完全相关。

问题A处理哈希空间和结果哈希空间之间的差异。当散列1KB文件(1024字节)时,散列有32个字节,将出现:

10907481356194159294629842447338E+2466(即带2466零的数字)输入文件的可能组合

散列空间将

11579208923731619542357098500869E+77(即77个零的数字)

差别很大。它们之间有2389个零。会发生冲突(冲突是一种特殊情况,当两个不同的输入文件具有完全相同的哈希值时),因为我们正在将10^2466个事例减少到10^77个事例。

最小化碰撞风险的唯一方法是扩大散列空间,从而使hahs变长。理想情况下,散列将具有文件长度,但这有点愚蠢。

第二个问题是性能。这只处理哈希算法。当然,较长的哈希值可能需要更多的CPU周期,但更智能的算法可能不需要。我对这个问题没有明确的答案。只是太难了。

但是,您可以对不同的散列实现进行基准测试/度量,并从中得出预先的结论。

祝你好运!)

Java字符串类所使用的简单哈希代码可以显示一个合适的算法。

下面是“GNU类路径”实现。(许可证: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;
  }

您可以使用knuth hash函数同时获取这两个函数 described here .

假设哈希表的大小为2的幂次方——只有一个乘法、一个移位、一个位和,这是非常快的。更重要的是(对你来说)它在减少碰撞方面非常出色(见 this analysis )

介绍了一些其他的好算法 here .

我喜欢StackOverflow!阅读这个问题让我更深入地研究哈希函数,我发现 Cuckoo Hash .

从文章中:

查找只需要检查两个 哈希表中的位置,其中 在最坏的情况下需要持续的时间 (见大O符号)。这是在 与许多其他哈希表相比 算法,可能没有 时间上的常量最坏情况限制 进行查找。

我认为这符合你的碰撞和性能标准。似乎权衡的是,这种类型的哈希表只能得到49%的满值。

下面是一种自己实现它的简单方法: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

以下是帖子中的一个片段:

如果假设我们有一个大写英文字母的字符集,那么字符集的长度是26,其中a可以用数字0表示,b可以用数字1表示,c可以用数字2表示,依此类推,直到z可以用数字25表示。现在,每当我们想将这个字符集的字符串映射到一个唯一的数字时,我们都会执行与二进制格式相同的转换。

“杂音散列”在性能和冲突方面都很好。

在“softwarengineering.stackexchange”中提到的线程有一些测试和杂音获胜。

我写了自己的C端口的杂音哈希2到.NET,并在466K的英文单词列表上测试了它,得到22个冲突。

结果和实施如下: https://github.com/jitbit/MurmurHash.net (免责声明,我参与了这个开源项目!)