为什么散列表取余时要模素数？

在构建散列表时，最常用的散列函数之一是除法散列函数，本文简单描述为什么除法散列函数取余时要模素数。

除法散列函数的形式如下： $$hash(N)=N\%M$$ 对于一个散列函数，其目的是将一个大的空间尽量均匀地映射到一个小的空间。那么对于上述形式的除法散列函数，我们想要的效果是对于任意的输入集合 $A$，其映射尽量均匀地分布在集合 $B = {0,1,2,…,M-1}$ 上。

容易想到，如果集合 $A$ 本身就是均匀分布的，类似于集合 ${1,2,3,4,…}$，那么 $M$ 的取值是无所谓的，集合 $A$ 总能被均匀映射到集合 $B$。但是，现实世界的输入往往不是如此，比如集合 $A$ 中可能大多数是偶数，那么最后的映射结果就会不均匀。

那么为什么取 $M$ 为素数可以解决这个问题呢？

我们可以假设 $M$ 不是素数，那么也就存在 $N$，在 $M=km$，$N=kn$ 时有 $km=kn$，其中 $k$ 是 $M$ 和 $N$ 的最大公约数。

设 $M\%N=r$，那么就有 $M=Nq+r$，其中 $q$ 是 $M$ 整除以 $N$ 的结果。

因此我们就有： $$M=km, N=kn, M=Nq+r$$ 代入得到： $$km=knq+r$$ 因为 $k\neq0$，所以可以得到： $$m=nq+\frac{r}{k}$$ 容易看出，$m$ 和 $nq$ 都是整数，那么 $\frac{r}{k}$ 也一定是整数，也就是说，此时 $r$ 的分布空间为 ${0,k,2k,3k,…,mk}$，是我们期望分布空间的 $\frac{1}{k}$。那么只要取 $k=1$ 我们就可以保证映射结果的均匀，即 $M$ 要为素数。

参考文献

1. Hash时取模一定要模质数吗？ - 我只想做一只懒猫的回答 - 知乎 https://www.zhihu.com/question/20806796/answer/159392465