数据结构课件Ch9_哈希表.ppt

《数据结构课件Ch9_哈希表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.3哈希表————动态查找表1哈希查找也称为散列查找它不同于前面介绍的几种查找方法。上述方法都是把查找建立在比较的基础上，而哈希查找则是通过计算存储地址的方法进行查找的。29.3.1什么是哈希表纵观以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系，因此，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。因此，用这类方法表示的查找表，其平均查找长度ASL都不为零，不同表示方法的差别仅在于：和给定值进行比较的关键字的顺序不同。3对于频繁使用的查找表，希望ASL=0。即不需要从“比较”的结果

2、来确定查找成功，只有一个办法：预先知道所查关键字在表中的位置，也就是说，记录在表中位置和其关键字之间存在一种确定的关系。4例如：为每年招收的1000名新生建立一张查找表，其关键字为xx000~xx999(前两位为年份)。则可以下标为000~999的顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。数据元素存储位置5但是，对于动态查找表而言，1)表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况，需建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。注意：这个函数

3、并不一定是数学函数。6例如：对于如下9个关键字{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324252613设f(key)=(Ord(第一个字母)-Ord('A')+1)/282961114127哈希表：ChenDeiHanLiQianSunChenYeZhao12345678910111213...8从这个例子可见，哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可;由

4、于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1key2，而f(key1)=f(key2)。并且，改进哈希函数只能减少冲突，而不能避免冲突。因此，在设计哈希函数时，一方面要考虑选择一个“好”的哈希函数;另一方面要选择一种处理冲突的方法。9所谓“好”的哈希函数，指的是，对于集合中的任意一个关键字，经哈希函数“映象”到地址集合中任何一个地址的概率是相同的。称这类哈希函数为“均匀的”哈希函数。哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存

5、储位置，这种表被称为哈希表。所得存储位置称为哈希地址(又称散列地址)。109.3.2哈希函数的构造方法对数字的关键字可有下列哈希函数的构造方法，若是非数字关键字，则需先对其进行数字化处理。111.直接定址法哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b如：k1,k2分别有值10、1000；选10、1000作为存放地址。简单、不经济。仅限于：地址集合的大小=关键字集合的大小自身函数122. 数字分析法假设关键字集合中的每个关键字都是由s位数字组成(k1,k2,…,kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。仅限于：能预先估计出全

6、体关键字的每一位上各种数字出现的频度，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。133．平方取中法此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，同时平方值的中间几位受到整个关键字中各位的影响;14设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同，即使其中有些字符相同。在平方取中法中，一般取散列地址为2的某次幂。

7、例如，若散列地址总数取为m=2r，则对内码的平方数取中间的r位。如果r=3，所取得的散列地址参看下图的最右一列。15标识符内码内码的平方散列地址A0101001A1013420420042A9014423420342B024004DMAX0415013021526443617100443DMAX104150130345264473522151420352AMAX01150130135423617100236A