07-7.5.2 散列函数的构造

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

设计散列函数时应该注意什么？

1. 定义域必须涵盖所有可能出现的关键字
2. 值域不能超出散列表的地址范围
3. 尽可能减少冲突。散列函数计算出来的地址应尽可能均匀分布在整个地址空间
4. 散列函数应尽量简单，能够快速计算出任意一个关键字对应的散列地址

除留余数法

$H(key)=key\%p$
散列表表长为 $m$，取一个不大于$m$但是最接近或等于m的质数$p$

注：质数又称素数。指除了1和此整数自身外，不能被其它自然数整除的树

适用场景：较为通用，只要关键字是整数即可

• 对合数取余，散列地址分布不均匀，易发生冲突
• 对质数区域，散列地址分布均匀，不易发生冲突

直接定址法

$H(key)=key或H(key)=a\ast key+b$
其中，$a$ 和 $b$ 是常数。这种方法计算最简单，且不会发生冲突。若关键字分布不连续，空位较多，则会造成存储空间的浪费。

适用场景：关键字分布基本连续

数字分析法

设关键字是 $r$ 进制数（如十进制数），而 $r$ 个数码在各位上出现的频率不一定相同

• 可能在某些位置上分布均匀一些，每种数码出现的机会均等；
• 而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址

适用场景：关键字集合已知，且关键字的某几个数码位分布均匀

平方取中法

具体取多少位要视实际情况而定
这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀

适用场景：关键字的每位取值都不够均匀

1. 先对关键字取平方
2. 再取平方的中间的几位（因为中间几位的值受每个数码位的影响）