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中详细讨论了这一点。