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

Question

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

1. 最小的哈希冲突
2. 性能

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

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

Answer 1

忘记"最好"一词.无论任何人可能提出哪种哈希算法,除非你有一组非常有限的数据需要进行哈希处理,否则每个平均表现非常好的算法如果只是被正确地提供(或从你的角度来看)就会变得完全无用"错误的"数据.

我没有浪费太多时间考虑如何在不占用太多CPU时间的情况下使哈希更加无冲突,而是开始考虑"如何使冲突更少问题".例如,如果每个哈希桶实际上都是一个表,并且该表中的所有字符串(具有冲突)按字母顺序排序,则可以使用二进制搜索(仅为O(log n))在存储桶表中进行搜索,这意味着,即使每隔一个哈希桶有4次冲突,你的代码仍然会有不错的性能(与无冲突表相比,它会慢一点,但不是那么多).这里的一大优势是,如果你的表足够大而你的哈希不是太简单,

实际上我之前有一种情况,在使用二进制搜索直接在排序表中搜索结果比哈希更快!即使我的哈希算法很简单,也需要花费相当长的时间来对值进行哈希处理.性能测试表明,只有当我获得超过700-800个条目时,散列确实比二进制搜索更快.但是,由于表格永远不会超过256个条目,并且平均表格低于10个条目,基准测试清楚地表明,在每个系统上,每个CPU,二进制搜索都更快.在这里,通常已经比较数据的第一个字节的事实足以导致下一个bsearch迭代(因为数据在前一个到两个字节已经非常不同)已证明是一个很大的优势.

总结一下:我会采用一种不错的哈希算法,它不会导致平均过多的冲突而且速度相当快(我甚至会接受更多的冲突,如果它只是非常快!)而是优化我的代码如何一旦碰撞发生,就会获得最小的性能损失(他们会这样做!除非你的哈希空间至少等于或大于你的数据空间,否则你可以将唯一的哈希值映射到每个可能的数据集).

Answer 2

正如Nigel Campbell所说,没有"最佳"散列函数这样的东西,因为它取决于你正在散列的数据特征以及你是否需要加密质量哈希.

也就是说,这里有一些指示:

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

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

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

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

  我也看到了代码只是将xor的哈希码放在一起,但这对我来说似乎是一个坏主意(尽管我再没有分析支持这一点).如果没有别的,如果相同的字符串以不同的顺序进行哈希处理,则最终会发生冲突.

• 我使用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

Answer 3

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

Answer 4

我会在这里跛脚,给出一个更理性的回答,而不是一个针对性的答案,但请取其中的价值.

首先,有两个不同的问题:

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

这两个问题是温和地相互关联的.它们并不完全相关.

问题是处理hashee和结果哈希空间之间的差异.当您散列1KB文件(1024字节)文件并且散列有32个字节时,将会:

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

并且哈希空间将具有

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

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

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

第二个问题是表现.这只涉及散列算法.当然,更长的哈希很可能需要更多的CPU周期,但更聪明的算法可能不需要.我对这个问题没有明确的案例答案.这太难了.

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

祝好运 ;)