与此哈希码函数进行HashCode冲突的可能性有多大？

Question

在以下场景中,与下面的函数发生HashCode冲突的可能性有多大.

1. 使用键[0],键[1],键[2],键[3]的随机int值
2. 使用具有以下约束的随机键值
   • 键[0] <1,000,000
   • key [1] <10,000
   • 关键[2] <1,000
   • 关键[3] <1,000

假设我们有1000万个对象.

int[] key=new int[4];    
public override int GetHashCode()
{
    // Use large prime multiples to create a unique hash key
    // Create the hash offsets using a "even powers of 2 minus 1" method, which gives 
    // primes most of the time.  
    int hashKey = 0;
    hashKey += 2047 * key[0];
    hashKey += 8191 * key[1];
    hashKey += 32767 * key[2];
    hashKey += 131071 * key[3];
    return hashKey;
}

Answer 1

这是一个奇怪的问题.让我们从代码中的明显错误开始:

// Use large prime multiples to create a unique hash key     
// Create the hash offsets using a "even powers of 2 minus 1" method, which gives      
// primes most of the time.   

首先,这些都是两减一的奇数幂; 它们都不是两减一的幂.

其次,在你选择作为"大素数倍数"的四个乘数中,其中一半不是素数.2047和32767是复合的.

第三,如果我们"纠正" - 并且我谨慎地使用了这个词 - 这个陈述是"2的奇数幂减去一个大部分时间给出素数的",这个陈述是荒谬的错误.这种形式的素数被称为梅森素数,并且只有47种已知的梅森素数.我向你们保证,梅森素数的密度远低于一半.这样说:在2 ^ 1-1和2 ^ 43112609-1之间的奇数梅森数,其中46个已知是素数,大约是五十分之一,而不是一半.

第四,你认为素数与任何东西有什么关系？素数有多少神话力量？当然重要的是哈希码的分布往往不会产生哈希表大小的倍数.由于哈希表大小被选择为素数,因此看起来这可能会加剧问题.

第五,散列键不是唯一的; 你的问题是关于它们何时发生碰撞,所以很明显它们不是唯一的.

第六,假设你的哈希函数在32位整数的空间中具有完全随机的分布.在生日"悖论"中,当从32位空间随机抽取一千万个数字时,你会发现至少有一次碰撞的可能性远大于99%.实际上,预期的碰撞次数大约为十万或二万.(我们可以计算出预期碰撞的确切数量,但是谁在乎它究竟是什么;它在那个数量级上.)

那太多碰撞了吗？比随机分布做得更好是非常困难的.如果您需要的冲突少于此次,那么您首先不应该使用32位哈希算法.

第七,谁关心哈希函数在其整个范围内有多少次碰撞？当然,实际问题应该是"这个散列如何与大表中的真实数据一起执行？" 与我们不同,您可以通过尝试来回答这个问题.如果它符合您的绩效预算,那就太好了,担心其他事情.如果没有,请在开始指责哈希函数之前找出原因.

我很困惑这个问题以及你希望从答案中得到什么.你可以解释吗？

Answer 2

我编写了一个快速脚本来测试这一点。

import random

def hash(key):
    hashKey = 0
    hashKey += 2047 * key[0]
    hashKey += 8191 * key[1]
    hashKey += 32767 * key[2]
    hashKey += 131071 * key[3]
    return hashKey

seen = set()
collisions = 0
for i in range(0,10000000):
    x = hash([random.randint(0,1000000), random.randint(0,10000), random.randint(0,1000), random.randint(0,1000)])
    if x in seen:
        collisions += 1
    else:
        seen.add(x)

print collisions

当我运行它时，它告诉我发生了 23735 次碰撞。我还在 100 万个元素上进行了尝试，得到了 247 次碰撞。这两个数字都是 4 次运行的平均值。