7.5.2 散列函数构造

除留余数法h(k)=k mod p常取不大于表长的质数p，以减少键模式与表长公因子。数字分析、平方取中、折叠等方法依赖关键字分布。评价重点是均匀，不是公式复杂。

手工推演

键多为10的倍数，若表长10直接取模则全落0；改用质数11会分散到多个桶。

结构与代码

字符串可用滚动哈希逐字符累积并取模；计算要防溢出，散列值只决定桶，键相等仍需原值比较。

正确性

若输入差异能影响多个低位/高位，桶分布更均匀；最终比较保证碰撞不误判相等。

错解反馈

把散列值相等当键相等；固定取键低位但数据低位相同；p超过实际桶数。

迁移训练

键[20,30,40,50]，模10和模11哪个更均匀？答案模11。