哈希函数中的冲突太多

Question

我试图将大约6400万个64位唯一无符号整数散列到1.28亿个桶(27位宽地址).我尝试了Bob Jenkin的HashLittle和Murmur哈希(这些哈希函数都提供了32位哈希值,我将其屏蔽以获得27位地址).在这两种情况下,它导致大约22%的碰撞,最终只占据了37%的水桶.这是预期还是我做错了什么？我期待更少的碰撞和更好的铲斗占领.

Answer 1

使用基于http://en.wikipedia.org/wiki/Poisson_distribution的近似值,它看起来比我预期的要差一些.如果桶中的预期条目数是1/2,我预计0个条目的概率大约是exp(-0.5)= 0.607,并且桶中1个条目的概率大约是这个的一半,或0.303.这使得存储桶具有两个或更多条目的概率为0.09.

你的整数都是独一无二的吗？如果没有,您是否计算重复值导致哈希冲突？

在有利的情况下,您可以选择一个哈希函数,以便给出随机期望的FEWER冲突.有时hash(x)= x%p,其中p是素数,将实现此目的.