将libnids哈希算法得到冲突？

问题描述：

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可以获得相同的散列值吗？将libnids哈希算法得到冲突？

输入大小大于哈希值，所以是的，根据[pidgeonhole原理]（http://en.wikipedia.org/wiki/Pigeonhole_principle）您的哈希函数不能是内射 –

答

你有96位，你试图散列到32位，所以在某个点发生碰撞的概率是100％。

假设您的散列函数生成均匀分布的值，生成65,536个32位散列值时发生冲突的几率非常接近50％。

我在文章Birthdays, Random Numbers, and Hash Keys中对此进行了一定的讨论。它包含了一个简单的公式，它可以根据生成的密钥大小和散列数量来估计碰撞可能性。

将libnids哈希算法得到冲突？

相关推荐