散列冲突和string性能方面的最佳散列algorithm

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

  1. 最小的哈希碰撞
  2. 性能

它不一定要安全。 基本上我试图创build一个基于一些对象的属性组合的索引。 所有的属性都是string

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

忘记“最好”这个词。 不pipe哪一个散列algorithm,任何人都可能提出,除非你有一个非常有限的一组数据,需要被散列,每一个平均执行得很好的algorithm,如果只被喂给正确的(或从你的angular度来看, “错”)的数据。

与其浪费太多时间思考如何在不占用太多CPU时间的情况下更容易实现散列,我宁愿开始考虑“如何使冲突更less问题”。 例如,如果每个哈希桶实际上都是一个表,并且该表(所有发生冲突)中的所有string按字母顺序sorting,则可以使用二分search(仅O(log n))在一个桶表内进行search,即使每个第二个散列桶有4个冲突,你的代码仍然会有不错的performance(与没有冲突的表相比,速度会慢一些,但是没有那么多)。 这里最大的一个好处是,如果你的表足够大,而且你的散列不是太简单,那么两个导致相同散列值的string通常看起来完全不同(因此二进制search可能会在平均可能有一两个字符后停止比较string;使每一个比较非常快)。

实际上,我自己有一个情况,直接在一个有序的表中使用二分查找结果比哈希快! 即使我的散列algorithm很简单,但是花了相当长的一段时间来散列这些值。 性能testing表明,只有当我得到超过约700-800个条目,散列确实比二分查找更快。 然而,无论如何,由于表格永远不会超过256个条目,并且由于平均表格低于10个条目,基准testing清楚地表明,在每个系统上,每个CPU,二进制search都更快。 在这里,通常已经比较了数据的第一个字节的事实足以导致下一个bsearch迭代(因为数据在第一个到第二个字节中已经非常不同了)成为一个很大的优势。

所以总结一下:我会采取一个体面的哈希algorithm,平均不会造成太多的碰撞,而且速度相当快(我甚至会接受更多的碰撞,如果速度非常快),而是优化我的代码一旦发生冲突就会得到最小的性能损失(除非你的散列空间至less等于或大于你的数据空间,并且你可以把唯一的散列值映射到每一个可能的数据集)。

正如奈格尔·坎贝尔(Nigel Campbell)指出的那样,“最佳”哈希函数并不存在,因为它取决于哈希值的数据特性以及是否需要密码哈希函数。

这就是说,这里有一些指针:

  • 由于您用作散列input的项目只是一组string,因此您可以简单地组合每个单独string的散列码。 我已经看到下面的伪代码build议这样做,但我不知道有什么特别的分析:

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

    根据这篇文章 ,System.Web有一个结合使用哈希码的内部方法

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

    我也看到了代码,只是异或的哈希码在一起,但这似乎是一个坏主意(尽pipe我再次没有分析来支持)。 如果没有别的,如果相同的string以不同的顺序散列,则最终会发生冲突。

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

  • 谢长廷有一篇像样的文章: http : //www.azillionmonkeys.com/qed/hash.html

  • 鲍勃·jenkins(Bob Jenkins)的另一篇很好的文章,最初于1997年在Dobb博士的杂志上发表(链接的文章有更新): http : //burtleburtle.net/bob/hash/doobs.html

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

我会在这里跛脚,给出一个更理论上的回应,而不是一个针对性的答案,但请把它的价值。

首先有两个不同的问题:

一个。 碰撞概率b。 散列的性能(即:时间,cpu周期等)

这两个问题是温和的核心。 他们并不完全相关。

问题a处理了hashee和哈希空间之间的区别。 当你散列一个1KB文件(1024字节)的文件,散列有32个字节时,将会有:

1,0907481356194159294629842447338e + 2466(即2466个零)可能的input文件组合

和散列空间将有

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

差异是巨大的。 它们之间有2389个零差异。 碰撞是一种特殊情况,当两个不同的input文件具有完全相同的哈希值时,会发生碰撞,因为我们将10 ^ 2466个案例减less到10 ^ 77个案例。

减less碰撞风险的唯一方法是扩大哈希空间,从而使哈希时间更长。 理想情况下,哈希将有文件的长度,但这是莫名其妙的。


第二个问题是性能。 这只处理哈希的algorithm。 当然,更长的哈希将可能需要更多的CPU周期,但更聪明的algorithm可能不会。 这个问题我没有明确的案例答案。 这太艰难了。

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

祝你好运 ;)

Java的String类使用简单的hashCode可能会显示一个合适的algorithm。

下面是“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; } 

你可以使用这里描述的Knuth哈希函数来得到两者。

这是非常快的假设2的幂次哈希表大小 – 只有一个乘法,一个移位,一个位和。 更重要的是(对你而言)在减less碰撞方面非常好(见本分析 )。

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

我爱Stackoverflow! 读这个问题让我再看看哈希函数,我发现了杜鹃哈希 。

从文章:

查找只需要检查哈希表中的两个位置,在最坏的情况下需要一定的时间(见大O符号)。 这与其他许多哈希表algorithm形成对照,哈希表algorithm在查找时可能没有常数最坏情况的约束。

我认为这符合你的碰撞和performance的标准。 看起来,折衷是这种types的散列表只能得到49%的满。

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

这是post的一个片段:

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