散列值计算的时候为什么要用到质数？

Question

散列值计算的时候为什么要用到质数？
这个质数怎么选择？比如137

Answer 1

最近刚学过，散列表解决冲突有两种方法，一是分离链接法，个人感觉和质数关系不大，第二种是开放定址法，如果非质数，碰撞几率较大，而且备选单元个数也会少很多。
我看得数据结构与算法分析一书。

Answer 2

正在了解这个散列， 在想能否通过建立质数key的时候判断是否表中已经含有key就跳过？不过可能多一次遍历，

Answer 3

听说过十七年蝉吗？

********补充 *****************

对于踩我的那几个同学，估计你们也没听过这个梗，我还是补充一下吧。

我回答的另一个问题：hashtable的size， 为什么一般选为质数？

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

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

那么

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

就会产生同样的值 6。