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 回答