哈希表大小为何是素数时冲突最少

在构造哈希函数的时候，可以利用求余的方法求出关键字所在的地址，其中，模最好是素数

这个链接解释的很明白（复制进入：https://blog.csdn.net/zhishengqianjun/article/details/79087525

作者举例了五个数列，通过对五个数列的实验，验证了作者的想法：取模运算的冲突与因子相关，因子越多，越容易冲突

事实确实如此，但是看完我好像没有恍然大悟的感觉..（可能太长了没特别仔细看吧

• 看完后，想了几句话说服了自己（下图为例

  1，4，7，10..关键字映射到数组其实就是：
  放完第一个数据后，每放一个数据，就往后走三步。

  • 表格一数组size为6，(1+3)%6=4，(4+3)%6=1。后面在位置14之间死循环，不均匀
  • 表格二数组size为7，(1+3)%7=4,(4+3)%7=0,(0+3)%7=3,(3+3)%7=6..均匀分布

  当数组size为7的时候均匀分布，6的时候死循环。出现死循环因为：每次走3步，3是数组size，6的因数
  因此：输入数据之间的跨度不能是数组size的因数，否则空间不均匀
  输入数据之间的跨度我们不能控制，因此只能让数组size的因数几乎没有，而素数就没几个因数，所以数组的size选择素数比较好