【参考答案】讨论11.1 在除留余数法中,为什么p要取素数？

陈越发表于2019年08月24日

如果p不是素数，设含有质因子q，也就是p=tq,其中q为素数，那么所有含有q因子的关键词其散列地址值均是q的倍数。比如，取p为12=4*3,那么3倍数的关键词（如：9、18、24、27、33等），其散列地址（9、6、0、3、9）也均是3的倍数。散列函数的要求是能尽量均匀映射。如果p不是素数，会使得与p有公约数的关键词被散列到特定的几个位置，增加了冲突的机会。