將libnids哈希算法得到衝突？

Question

u_int 
mkhash (u_int src, u_short sport, u_int dest, u_short dport) 
{ 
    u_int res = 0; 
    int i; 
    u_char data[12]; 
    u_int *stupid_strict_aliasing_warnings=(u_int*)data; 
    *stupid_strict_aliasing_warnings = src; 
    *(u_int *) (data + 4) = dest; 
    *(u_short *) (data + 8) = sport; 
    *(u_short *) (data + 10) = dport; 
    for (i = 0; i < 12; i++) 
    res = ((res << 8) + (data[perm[i]]^xor[i])) % 0xff100f; 
    return res; 
} 

這裏是上面的libnids哈希算法。當表大小爲65536時，兩個不同的tuple4可以獲得相同的散列值嗎？

Answer 1

你有96位，你試圖散列到32位，所以在某個點發生碰撞的概率是100％。

假設您的散列函數生成均勻分佈的值，生成65,536個32位散列值時發生衝突的機率非常接近50％。

我在文章Birthdays, Random Numbers, and Hash Keys中對此進行了一定的討論。它包含了一個簡單的公式，它可以根據生成的密鑰大小和散列數量來估計碰撞可能性。