53

如果我们有以下优先级(按此顺序),那么最好的散列算法是什么:

  1. 最小的哈希冲突
  2. 表现

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

任何对 c# 实现的引用将不胜感激。

4

9 回答 9

33

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

与其浪费太多时间考虑如何在不使用过多 CPU 时间的情况下让哈希更无冲突,我宁愿开始考虑“如何减少冲突问题”。例如,如果每个哈希桶实际上是一个表,并且该表中的所有字符串(发生冲突)都按字母顺序排序,您可以使用二进制搜索(仅 O(log n))在桶表中搜索,这意味着,即使每个第二个哈希桶有 4 次冲突,您的代码仍然会有不错的性能(与无冲突表相比会慢一些,但不会那么多)。这里的一大优势是,如果你的表足够大并且你的哈希不是太简单,

实际上,在使用二进制搜索直接在排序表中搜索结果比散列更快之前,我自己也遇到过这种情况!尽管我的散列算法很简单,但散列值需要相当长的时间。性能测试表明,只有当我得到超过 700-800 个条目时,散列确实比二分查找快。但是,由于该表无论如何都不会超过 256 个条目,并且平均表低于 10 个条目,因此基准测试清楚地表明,在每个系统、每个 CPU 上,二进制搜索都更快。在这里,通常已经比较数据的第一个字节足以导致下一次 bsearch 迭代的事实(因为数据过去在第一个到两个字节中已经非常不同)结果证明是一个很大的优势。

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

于 2008-11-03T21:18:30.237 回答
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 年发表在 Dobb 博士的期刊上(链接的文章有更新):http ://burtleburtle.net/bob/hash/doobs.html

于 2008-10-30T19:23:14.983 回答
8

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

于 2008-10-30T19:08:33.220 回答
8

我将在这里跛脚并给出更理论的回答而不是精确的答案,但请接受其中的价值。

首先有两个明显的问题:

一种。碰撞概率 B. 散列的性能(即:时间、CPU 周期等)

这两个问题有轻微的关联。它们不是完全相关的。

问题 a 处理哈希值和生成的哈希空间之间的差异。当您散列一个 1KB 文件(1024 字节)文件并且散列有 32 个字节时,将有:

1,0907481356194159294629842447338e+2466(即一个有 2466 个零的数字)输入文件的可能组合

并且哈希空间将有

1,1579208923731619542357098500869e+77(即有77个零的数字)

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

最小化冲突风险的唯一方法是扩大哈希空间,从而使哈希更长。理想情况下,哈希将具有文件长度,但这在某种程度上是愚蠢的。


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

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

祝你好运 ;)

于 2008-10-31T00:57:16.010 回答
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;
  }
于 2008-10-30T19:20:59.310 回答
2

您可以使用此处描述的 Knuth 哈希函数获得两者。

假设哈希表大小为 2 次方,它的速度非常快——只有一次乘法、一次移位和一位与。更重要的是(对您而言)它非常适合最小化碰撞(请参阅此分析)。

这里描述了一些其他好的算法。

于 2008-10-30T19:14:43.080 回答
1

这是杜鹃哈希

查找只需要检查哈希表中的两个位置,在最坏的情况下需要恒定的时间(请参阅大 O 表示法)。这与许多其他哈希表算法形成对比,后者在查找时间上可能没有恒定的最坏情况限制。

我认为这符合您的碰撞和性能标准。看来权衡是这种类型的哈希表只能填满 49%。

于 2008-10-30T20:11:28.053 回答
1

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

这是该帖子的一个片段:

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

于 2015-04-17T03:32:23.723 回答
1

“Murmurhash”在性能和碰撞方面都相当不错。

“softwareengineering.stackexchange”中提到的线程进行了一些测试,并且 Murmur 获胜。

我将我自己的 MurmurHash 2 的 C# 移植到 .NET 并在 466k 英文单词列表上对其进行了测试,得到了 22 次冲突。

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

于 2018-03-08T20:57:44.493 回答