如果我们有以下优先级(按此顺序),那么最好的散列算法是什么:
- 最小的哈希冲突
- 表现
它不一定是安全的。基本上我正在尝试根据某些对象的属性组合创建索引。所有属性都是字符串。
任何对 c# 实现的引用将不胜感激。
忘记“最好”这个词。无论任何人可能想出哪种哈希算法,除非您有一组非常有限的数据需要进行哈希处理,否则每个平均性能非常好的算法如果只提供正确的(或从您的角度来看)可能变得完全无用“错误”)数据。
与其浪费太多时间考虑如何在不使用过多 CPU 时间的情况下让哈希更无冲突,我宁愿开始考虑“如何减少冲突问题”。例如,如果每个哈希桶实际上是一个表,并且该表中的所有字符串(发生冲突)都按字母顺序排序,您可以使用二进制搜索(仅 O(log n))在桶表中搜索,这意味着,即使每个第二个哈希桶有 4 次冲突,您的代码仍然会有不错的性能(与无冲突表相比会慢一些,但不会那么多)。这里的一大优势是,如果你的表足够大并且你的哈希不是太简单,
实际上,在使用二进制搜索直接在排序表中搜索结果比散列更快之前,我自己也遇到过这种情况!尽管我的散列算法很简单,但散列值需要相当长的时间。性能测试表明,只有当我得到超过 700-800 个条目时,散列确实比二分查找快。但是,由于该表无论如何都不会超过 256 个条目,并且平均表低于 10 个条目,因此基准测试清楚地表明,在每个系统、每个 CPU 上,二进制搜索都更快。在这里,通常已经比较数据的第一个字节足以导致下一次 bsearch 迭代的事实(因为数据过去在第一个到两个字节中已经非常不同)结果证明是一个很大的优势。
所以总结一下:我会采用一个不错的哈希算法,它不会导致太多的平均冲突并且相当快(如果它非常快,我什至会接受更多的冲突!)而是优化我的代码如何一旦发生冲突,获得最小的性能损失(他们会的!除非您的哈希空间至少等于或大于您的数据空间,并且您可以将唯一的哈希值映射到每个可能的数据集)。
正如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
没有一种单一的最佳散列算法。如果您有一个已知的输入域,您可以使用完美散列生成器(例如gperf)来生成散列算法,该算法将在该特定输入集上获得 100% 的比率。否则,这个问题就没有“正确”的答案。
我将在这里跛脚并给出更理论的回答而不是精确的答案,但请接受其中的价值。
首先有两个明显的问题:
一种。碰撞概率 B. 散列的性能(即:时间、CPU 周期等)
这两个问题有轻微的关联。它们不是完全相关的。
问题 a 处理哈希值和生成的哈希空间之间的差异。当您散列一个 1KB 文件(1024 字节)文件并且散列有 32 个字节时,将有:
1,0907481356194159294629842447338e+2466(即一个有 2466 个零的数字)输入文件的可能组合
并且哈希空间将有
1,1579208923731619542357098500869e+77(即有77个零的数字)
差异是巨大的。它们之间有 2389 个零差。因为我们将 10^2466 个案例减少到 10^77 个案例,所以会有冲突(当两个不同的输入文件具有完全相同的哈希时,冲突是一种特殊情况)。
最小化冲突风险的唯一方法是扩大哈希空间,从而使哈希更长。理想情况下,哈希将具有文件长度,但这在某种程度上是愚蠢的。
第二个问题是性能。这仅涉及哈希算法。当然,更长的哈希很可能需要更多的 CPU 周期,但更智能的算法可能不需要。对于这个问题,我没有明确的案例答案。这太难了。
但是,您可以对不同的哈希实现进行基准测试/测量并从中得出预结论。
祝你好运 ;)
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;
}
这是杜鹃哈希。
查找只需要检查哈希表中的两个位置,在最坏的情况下需要恒定的时间(请参阅大 O 表示法)。这与许多其他哈希表算法形成对比,后者在查找时间上可能没有恒定的最坏情况限制。
我认为这符合您的碰撞和性能标准。看来权衡是这种类型的哈希表只能填满 49%。
这是自己实现它的简单方法:http: //www.devcodenote.com/2015/04/collision-free-string-hashing.html
这是该帖子的一个片段:
如果说我们有一个大写英文字母的字符集,那么字符集的长度是 26,其中 A 可以用数字 0 表示,B 可以用数字 1 表示,C 可以用数字 2 表示,依此类推,直到 Z 用数字表示25. 现在,每当我们想将此字符集的字符串映射到唯一数字时,我们执行与二进制格式相同的转换
“Murmurhash”在性能和碰撞方面都相当不错。
“softwareengineering.stackexchange”中提到的线程进行了一些测试,并且 Murmur 获胜。
我将我自己的 MurmurHash 2 的 C# 移植到 .NET 并在 466k 英文单词列表上对其进行了测试,得到了 22 次冲突。
结果和实现在这里:https ://github.com/jitbit/MurmurHash.net (免责声明,我参与了这个开源项目!)