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

Question

如果我们有以下优先级(按此顺序)，最好的哈希算法是什么:

1. 最少的散列冲突
2. 表现

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

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

Answer 1

忘掉“最好”这个词吧。无论任何人可能想出哪种散列算法，除非您需要散列的数据集非常有限，否则如果仅提供正确的(或从您的角度来看)，则平均表现非常好的每个算法都可能变得完全无用“错误”)数据。

与其浪费太多时间考虑如何在不使用太多 CPU 时间的情况下使散列更无冲突，我宁愿开始考虑“如何减少冲突问题”。例如。如果每个散列桶实际上是一个表，并且该表中的所有字符串(发生冲突)都按字母顺序排序，您可以使用二进制搜索(仅 O(log n))在桶表中进行搜索，这意味着，即使当每第二个哈希桶有 4 次冲突时，您的代码仍将具有不错的性能(与无冲突表相比，它会慢一点，但不会慢那么多)。这里的一大优势是，如果您的表足够大并且您的散列不太简单，则导致相同散列值的两个字符串通常看起来完全不同(因此二分查找可以在平均一两个字符后停止比较字符串; 使每次比较都非常快)。

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

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