第9章 查找 part4

《第9章 查找 part4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九章查找主讲：戚玉涛第九章查找9.1查找的基本概念9.2静态查找表——基于线性表的查找法9.3动态查找表——基于树表的查找法9.4哈希表——计算式查找法哈希表前面介绍的内容中，记录在文件中的存储地址是随机的，即记录在表中的位置和它的关键字之间不存在一个确定的关系。200302200305200301张三李四王五192120200305200301200302李四王五张三212019学号姓名年龄010203查找某一条记录需要进行一系列的“比较”。查找的效率依赖于比较的次数。哈希表用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：关键字和给定

2、值进行比较的顺序不同。对于频繁使用的查找表，希望ASL=0。只有一个办法：预先知道所查关键字在表中的位置。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。此对应关系称为哈希函数。可以通过哈希函数从关键字直接计算出记录在表中位置。哈希表的基本概念哈希法的思想：在元素的关键字Key和元素的存储位置p之间建立一个对应关系H，使p=H(Key)。哈希法又称散列法、杂凑法或关键字地址计算法等。哈希函数：H称为哈希函数(散列函数)，是一个压缩映象，是从关键字空间到存储地址空间的一种映象。当查找关键字为k的元素时，利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关

3、键字直接存取元素的目的。哈希表的基本概念哈希地址：H(Key)也称为哈希地址或散列地址哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。哈希表的例子：30个地区的各民族人口统计表编号地区别总人口汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shan

4、ghai)=19H(Shenyang)=19从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即k1≠k2，但H(k1)=H(k2)，这种现象称为“冲突”，此时称k1和k2为“同义词”。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。综上所述，哈希法主要包括以下两方面的内容：(1)如何构造哈希函数；(2)如何处理冲突。哈希函数构造方法1、直接定址法2、数字分析法3、平方取中法4、折叠法5、除留余数法6、伪随机数法哈

5、希函数构造方法1、直接定址法取关键字或关键字的某个线性函数值为哈希地址。直接定址法的哈希函数H(key)为：H(key)=key或H(key)=a×key+b计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可用直接定址法的哈希函数；否则，若关键字分布不连续将造成内存单元的大量浪费。直接定址法的例子(i)例，以年龄作为关键字(ii)例，统计解放后出生人口，以出生年份作为关键字地址出生年份011949021950231971481996..................H(key)=key–1949+1哈希函数构造方法2、数字分析法假设关键字集合中的每个关键字都

6、是由s位数字组成(u1,u2,…,us)；分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址数字分析法的例子哈希函数构造方法3、平方取中法当无法确定关键字中

7、哪几位分布较均匀时，取关键字平方后的中间几位作为哈希函数。实验证明:一个数字的平方值的中间部分通常对各位数字都比较敏感。故不同关键字会以较高的概率产生不同的哈希地址。平方取中法的例子200524200502012005022005032005X402098745764020105200400144120025X20048422002501024320025209820101441取4位48420243哈希函数构造方法4、折叠法将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为哈希函数。两种叠加处理的方法：移位叠加：将分割后的几部分