algorithm - 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

You have 96 bits that you're trying to hash into 32 bits, so the probability of collision occurring at some point is 100%.

Assuming that your hash function generates uniformly distributed values, the chance of collision when generating 65,536 32-bit hash values is pretty close to 50%.

I discussed this at some length in my article Birthdays, Random Numbers, and Hash Keys. It includes reference to a simple formula that can estimate the likelihood of collision given a key size and number of hashes generated.