第七章 哈希表.pptVIP

哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关。第一:与装填因子有关所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即=n/m。当越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。7-1-3哈希表的查找及性能分析第29页，共41页，星期日，2025年，2月5日IOTekInformationTchnology第七章哈希表第1页，共41页，星期日，2025年，2月5日哈希表第七章第2页，共41页，星期日，2025年，2月5日预习检查哈希表的定义处理冲突的方法有那些第3页，共41页，星期日，2025年，2月5日本章目标了解什么是哈希表掌握如何构造哈希函数处理冲突的方式哈希表的查找及分析第4页，共41页，星期日，2025年，2月5日本章结构处理冲突的方法哈希表哈希函数的构造方法什么是哈希表第5页，共41页，星期日，2025年，2月5日7-1哈希表哈希表又称散列表。哈希表存储的基本思想是：以数据表中的每个记录的关键字k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。第6页，共41页，星期日，2025年，2月5日例如，要将关键字值序列（3，15，22，24），存储到编号为0到4的表长为5的哈希表中。计算存储地址的哈希函数可取除5的取余数算法H(k)=k%5。则构造好的哈希表如图所示。7-1哈希表第7页，共41页，星期日，2025年，2月5日7-1哈希表理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突。把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。在大多数情况下，冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大，而对应的地址数则可能比较少。对于哈希技术，主要研究两个问题：（1）如何设计哈希函数以使冲突尽可能少地发生。（2）发生冲突后如何解决。第8页，共41页，星期日，2025年，2月5日构造好的哈希函数的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。1．直接定址法直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)为：H(k)=k+c(c≥0)这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。7-1-1哈希函数的构造方法第9页，共41页，星期日，2025年，2月5日例：统计某地区从1949年到1995年每年出生的人数，列在一张表中。年份为关键字，因共有47年，所以表中位置范围是1～47。设置H(k)=k-1948即可，其中k为年份数。这样的哈希表示意如下：若要查1970年的出生人数，则根据（1970-1948=22）计算，在表的第22个位置即可找到。7-1-1哈希函数的构造方法第10页，共41页，星期日，2025年，2月5日2．除留余数法取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即：H(k)=k％m这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度m。使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明，在m取值为素数（质数）时，冲突可能性相对较少。7-1-1哈希函数的构造方法第11页，共41页，星期日，2025年，2月5日3．平方取中法取关键字平方后的中间几位作为哈希函数地址（若超出范围时，可再取模）。设有一组关键字ABC，BCD,CDE，DEF，……其