全部博文（610）
分类：
2012-06-20 11:20:34
原文地址：Hash表与素数 作者：gaofei8530
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种可能，这样显然会增加冲突的概率。
