【摘要】：首先来看散列函数的设计原则。散列函数要简单，计算散列函数花费时间为O。根据这4个设计原则，下面介绍几种常用的构造散列函数的方法。通常选p为不大于散列表容量的最大素数。将关键字值k的平方k2的中间几位作为Hash的值，位数取决于散列表的长度。例如，k=4 371，k2=22 382 361，若表长为100，取中间两位，则Hash=82。散列函数的构造方法还有直接定址法、数字分析法、随机数法等，有兴趣的同学可参考有关资料。
首先来看散列函数的设计原则。
（2）散列函数要简单，计算散列函数花费时间为O(1)。
（3）要使关键字的所有成分都起到作用，以反映不同关键字的差异。
（4）还要考虑进行查找时数据元素的查找频率。
根据这4个设计原则，下面介绍几种常用的构造散列函数的方法。
（1）除留余数法。
这是一种最简单也最常用的构造散列函数的方法。取关键字被某个不大于散列表表长m的数p除后所得的余数作为散列地址，即(www.xing528.com)
这一方法的关键在于p的选择。例如，若选p为偶数，则得到的散列地址总是将奇数键值映射成奇数地址，偶数键值映射成偶数地址，就会增加冲突发生的机会。通常选p为不大于散列表容量的最大素数。比如，散列表容量m=1 000，选择p时应选择不大于1 000的最大素数p=997。
（2）平方取中法。
将关键字值k的平方k2的中间几位作为Hash(k)的值，位数取决于散列表的长度。
例如，k=4 371，k2=22 382 361，若表长为100，取中间两位，则Hash(k)=82。
（3）折叠法。
将关键字分成几部分，按照一定的规则将几部分再组合到一起得到关键字的Hash值。
散列函数的构造方法还有直接定址法、数字分析法、随机数法等，有兴趣的同学可参考有关资料。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
