hashtable的size， 为什么一般选为质数？

Question

设计hashtable时，size一般是prime number， 这是为什么呢。。。

Answer 1

你肯定没有听说过 17年蝉 的故事吧。

用质数是为了防止冲突。比如一个hashtable（长度为3）的哈希算法是：

a[0]*1 + a[1]*2 + a[2]*4

那么

[0,1,1] 
[2,2,0]
[4,1,0]
[2,0,1]
…… 

就会产生同样的值 6。

Answer 2

其实主要因为哈希容量影响哈希函数的确定, 而一般常用的哈希方式如取模等, 如果是随机分布的整数，那么哈希模数只要取到足够大，在概率上来说都是一样的，但是这显然脱离实际应用.

一般地说, 当模数非常大的时候, 取什么数关系不太大, 质数合数都有不错的结果,但是一般情况下模数不会 "足够大" , 这个时候, "所有" 17以上的质数都有不错的结果, 而很多合数也有不错的结果, 但是个别一些合数结果会 非常非常差 冲突非常多. 因此为了稳妥起见, 取17以上的质数.

Answer 3

我觉得仅仅是为了避免那些差的哈希算法。如果某个哈希算法把 size 作为除数，那么就容易产生因为约分导致的聚集。