Hash表与素数

1760阅读 0评论2013-09-04 cjdao
分类:Mysql/postgreSQL

Q:当hash表满的时候,为何hash表size总是扩展成一个素数。
A:素数可以有效的减少hash冲突。

假设hash表大小为size,这是一个合数,即有size=a*n。当有hash值为hashcode,且hashcode = b*n.
则hashcode取模之后为:
hashcode = hashcode%size = hashcode - (hashcode / size) * size = hashcode - (b/a) * size
因为a是固定的,那么上面的hashcode的取值只有b种可能,这样显然会增加冲突的概率。

上一篇:POSIX 线程取消点的 Linux 实现
下一篇:开源代码分析技巧之——打印调用逻辑