散列表和素数

理解自：邓俊辉老师 《数据结构：散列》 -以蝉为师

我们假设有两个散列hash_a和hash_b,表a的长度M = 7,表b的长度M = 8。假设我们从1的位置开始，步长为2的产生数据。
那么产生的数据即为1,3,5,7,9,11···
我们将他们映射到表a和表b中，假设数据就到1000

0	1	2	3	4	5	6
72	71	72	71	72	72	72

我们可以看到足迹是遍历了整个表。
换到表2。

0	1	2	3	4	5	6	7
0	125	0	125	0	125	0	125

非常明显的看到堆积问题。
这是为什么呢？原因非常简单，因为当任意步长为表长的因子时，总会出发回到原点（循环），导致堆积。
假设表长M和步长S有则必然(i + nS)%M =( i%M + nS%M)%M = (i + nk)%M（大概是吧，因为还没学数论这里大概推导了一下）
解决的办法就是让GCD表示最大公约数，S为任意步长，M为表长。那么很明显M必须为素数。
那么应用到自然科学中，蝉的寿命在11和17这两个素数，假设蝉的天敌寿命为M，则蝉必然换代的年份平均分布在这个hash表（天敌的寿命）中。 如果为合数，则容易发生蝉的数量的堆积，被天敌吃完。