数据结构第22讲哈希表和插入排序

《数据结构第22讲哈希表和插入排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章查找9.1静态查找表9.2动态查找表9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析9.3.1什么是哈希表哈希表技术的主要目标是提高查找效率。1.哈希函数：根据关键字直接计算出元素所在位置的函数。例：设哈希函数为：H(K)=K/3+1，则构造关键字序列为1、2、5、9、11、13、16、21、27的散列表（哈希表）为：序号12345678910H(K)159131621272112.冲突两个不同的关键字具有相同的存储位置。序号123456

2、78910H(K)159131621272113.哈希表根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。(1)装填因子α；装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的

3、比值，即α=n/m（α<=1）。α越小，发生冲突的可能性越小，反之，发生冲突的可能性就越大。但是，α太小又会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。(2)所构造的哈希函数;(3)解决冲突的方法。①构造好的哈希函数，使冲突尽可能的少②设计有效的解决冲突的方法第9章查找9.1静态查找表9.2动态查找表9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析9.3.2哈希函数的构造方法例：关键码集合为{100，300，500，700，80

4、0，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：1.直接定址法取关键字或关键字的某个线性函数值为散列地址，即（K）=K或H（K）=a*K+b（其中a、b为常数）。0123456789900800700500300100优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。缺点：要占用连续地址空间，空间效率低。2.除后余数法取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。即H（K）=Kmodp（p≤m）经验得知：一般可选p为质数或不包含小于20的质因素

5、的合数。3.平方取中法取关键字平方后的中间几位为哈希函数。因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。34705243491487348269634852703486305349805834796713473919例：有一组（例如80个）关键码，其样式如下：讨论：①第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选

6、用。位号：①②③④⑤⑥⑦②若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。4.数字分析法5.折叠法是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。适用于：每一位上各符号出现概率大致相同的情况。移位法：将各部分的最后一位对齐相加。间界叠加法：从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,移位法：427＋518＋96=104

7、1间界叠加法：42751896—>724+518+69=13116.随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素：(1)计算哈希函数所需时间(包括硬件指令的因素)；(2)关键字的长度；(3)哈希表的大小；(4)关键字的分布情况；(5)记录的查找频率。第9章查找9.1静态查找表9.2动态查找表9.3哈希表9.3.1什么是哈

8、希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析9.3.3处理冲突的方法1.开放地址法开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。（1）线性探测法设散列函数H（K）=Kmodm（m为表长），若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为：Hi=(H(K)+di)modm(