为什么我的ELF哈希实现具有如此高的冲突率

Question

我目前正在努力选择一些用于Object.GetHashCode()覆盖的通用散列函数.最初,根据本网站的推荐,我开始使用ELF.我的C#实现如下:

public int Generate(byte[] key) {
    const uint c = 0xf0000000;

    uint h = 0,
         g = 0;

    unchecked {
        for (int i = 0, len = key.Length; i < len; i++) {
            h = (h << 4) + key[i];

            if ((g = h & c) != 0)
                h ^= g >> 24;

            h &= ~g;
        }
    }

    return (int)h;
}

我的测试用例包括524,288个唯一值,分为短(1-64)和长(256-2048)字符串(有限的ASCII字符集)和任意二进制数据(每个131,072),以在各种情况下测试每个算法.

我也理解这个测试场景的局限性.散列算法在散列(例如URL)时可能表现异常,但在散列JPG或其他东西时可能会很糟糕.在我看来,随机字符串/二进制是选择通用函数的最佳起点.我很高兴听到为什么不是这种情况的原因.

我执行了3次单独的测试运行(每次生成一组新的随机字符串/字节)并对结果进行平均.

与我正在测试的其他算法相比,ELF算法产生了可怕数量的冲突:

• 短串:817次碰撞(约0.5%失败率).
• 短二进制:550次冲突(~0.4%失败率)
• 长串/二进制:34次冲突(~0.025%失败率).

为了将其置于上下文中,我测试的其他3种算法平均在相同测试的平均3-10次碰撞之间产生.它也是4中最慢的,所以在这一点上它似乎完全没用.

完整结果:

           Strings     Binary
Algorithm  short:long  short:long
ELF        817:40      550:28
FNV        1.6:2       0.6:2.6
OAT        9:9.6       14:5
Jenkins*   2:1.3       12:3.6

* A close approximation of the lookup3 hash function.

因此,对于ELF正在努力的相同随机样本(我已经生成了3个单独的集合),所有其他测试的算法正在以更少的冲突产生方式.

我已经搜索了ELF算法的变体,但我发现的几个例子似乎与我实现的一致.我见过的唯一变化是在这个问题上:使用ELF生成一个调整的hashmap.该变化包括h &= g >> 24在if块内,并将结果剪辑为31位.我测试了这种变化,它产生了同样可怕的结果.

我做过一些微妙但可怕的错误吗？我无法理解为什么它的表现如此糟糕,因为据称它在Unix中被广泛使用.

Answer 1

它不是加密哈希,它是哈希表哈希.

对于旨在用于散列表的散列函数,这是完全合理的性能.通常,您将存储数百到数十万个对象,并希望快速存储和检索对象.

你可以通过划分为桶来实现这一点,每个桶都包含一个链表(或者一个数组).然后计算哈希值,并在除以桶的数量时取余数,找到桶.然后,您将遍历链接列表,比较每个对象以找到您想要的对象.

如果存储桶为空,则找不到该对象.然后,您可以根据应用程序创建一个或采取其他适当的操作.

散列表的大小应该与预期存储的项目数量(或更多)具有大致相同的桶数,因此大多数搜索将找到具有零个,一个或两个条目的存储桶.

对于性能,您希望平衡计算哈希的费用与在遇到冲突时遍历非常短的链表的费用.考虑到这一点,设计了ELF和类似用途的散列函数的实现.

简而言之:

• 在散列表中,偶尔的碰撞是值得为更快的散列支付的价格.
• 在加密哈希中,慢哈希值是为避免冲突而付出的代价.

如果碰撞是您的应用程序中的问题,请使用SHA1或SHA256或设计时考虑到这一点.

注意:为了用作object.GetHashCode()的实现,哈希代码仅用于加速比较("快速失败")和用于哈希表.你不需要它完全抵抗,因为如果你碰撞,你将回到完全相等的比较.你需要平衡的表现.我建议只挖掘最重要的字段(使用它们自己GetHashCode())并对值进行异或.

编辑:另请参阅这些哈希:

• http://www.burtleburtle.net/bob/hash/doobs.html

Answer 2

在32位散列上的524000个随机样本中预期的冲突数是34.

你得到34个长字符串冲突,所以对于长字符串,这个算​​法或多或少地按预期执行.

由于数据中的熵少得多,所以哈希冲突在短字符串上的可能性要大得多,所以对于我来说,在小字符串上获得的性能要差一些,这绝不令我感到惊讶.

这是 suprising你得到只有十与其他的哈希算法的碰撞.我本以期待更多.

关于原始速度性能的主题:你可能会更好地停止这么聪明.抖动可以识别并优化极其常见的模式:

for(int i = 0; i < array.Length; ++i)
    do something with array[i]

以避免重新计算长度并避免对阵列访问进行范围检查.通过尝试聪明并避免重新计算长度,您可能会愚弄抖动,不再优化距离检查.

如果您希望始终避免范围检查,您可以随时使用不安全的代码; 将数组固定到位,获取指向它的指针,然后递增指针,就像你在C中编写程序一样.你负责确保那时的内存安全,但是几率很高它会更快.

当然,那种"扶手椅"性能分析正是你所付出的代价; 要获得真实的分析,试试看看会发生什么.

Answer 3

实际的 ELF 实现返回unsigned long，并且源unsigned long在内部使用。我不能肯定地说，但我的直觉是，您的实现只是通过处理int.