Question

此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：

f(key)=key mod p(p≤m)

mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

很显然，本方法的关键就在于选择合适的p，p如果选得不好，就可能会容易产生同义词。

例如表8-10-4，我们对于有12个记录的关键字构造散列表时，就用了f(key)=key mod 12的方法。比如29 mod 12=5，所以它存储在下标为5的位置。

表8-10-4

不过这也是存在冲突的可能的，因为12=2×6=3×4。如果关键字中有像18(3×6)、30(5×6)、42(7×6)等数字，它们的余数都为6，这就和78所对应的下标位置冲突了。

甚至极端一些，对于表8-10-5的关键字，如果我们让p为12的话，就可能出现下面的情况，所有的关键字都得到了0这个地址数，这未免也太糟糕了点。

表8-10-5

我们不选用p=12来做除留余数法，而选用p=11，如表8-10-6所示。

图8-10-6

此就只有12和144有冲突，相对来说，就要好很多。

因此根据前辈们的经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。