关于散列表中除留余数法构造的散列函数,除数选择素数的疑问

正在学习数据结构里的散列相关知识,书里一般都会提到,如果用除留余数的散列函数,最好选择素数作为除数。但没有对此详细的证明。

对此不太理解,个人理解是,无论素数还是合数,在取模的一个周期内都是均匀分布的单射的,并不会因为除数有质因数改变分布和冲突情况。

看了一些其他文章,也没有具有普遍性的证明。有的文章中会用一个特例来说明素数作除数更好,但特例不能证明一般性(例如有的文章中会拿一个具有公因数3的数列为key,然后mod6,结果表明这些key都被散列在0、3、6的地址上,以此来说明除数不应该用合数。但这个观点显然站不住脚,因为我也可以举一个具有公因数7的序列为key来mod7,也会造成严重冲突,而7是素数)

对于平常的应用中,如果散列的key通常不具有普遍的规律(例如都是某个数的倍数)而更倾向于随机性(比如储存一些号码,没有特殊规律),在这种随机输入的情况下是不是除数是否是素数不影响散列产生冲突的情况?如果依然有影响,能否有详细的具有普适性的证明

本人才疏学浅,想不通这个问题,特来请教

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!