静态查找表章作业课件chap9-2014.pptx

19.1静态查找表

9.1.1顺序表的查找

9.1.2有序表的查找

9.1.4索引顺序表的查找9.2动态查找表9.2.1二叉排序树和平衡二叉树9.2.2B-和B+树9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析第九章查找

2哈希查找 又叫散列查找，利用哈希函数进行查找的过程。基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系f,称这个对应关系为哈希函数，按这个思想建立的表为哈希表。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成，addr(ai)=H(ki)，其中：ai是表中的一个元素addr(ai)是ai的存储地址，ki是ai的关键字。9.3.1哈希表的相关定义

3例30个地区的各民族人口统计表编号地区名总人口汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区名作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19哈希法又称散列法、杂凑法或关键字地址计算法等。

4哈希函数是一个映像，因此设定很灵活，只要使得任何关键字由此得到的哈希函数值都落在表长允许范围之内即可。哈希函数并不一定是一对一的，例如，当m＞n时，对任何哈希函数H，至少存在两个关键字Ki≠Kj，使得H(Ki)=H(Kj)，这种对不同关键字而得到同一地址的现象，成为冲突。此时称ki和kj为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。综上所述，哈希法主要包括以下两方面的内容：如何构造哈希函数；如何处理冲突。

5因此，哈希表也可以描述为：根据给定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集上的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

6一般来说，只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值，如上例中城市和地区的可能出现值不下几百几千而地址集合的大小只有26，所以哈希函数是一个压缩映象，就不可避免产生冲突。在定义哈希表时既要定义好哈希函数又要给出处理冲突的方法。

7因此，在应用哈希查找方法时，主要要解决两个技术问题：一是构造好哈希函数的方法;二是研究解决冲突的方法。设计哈希函数一般应遵循以下原则：计算简单容易，哈希函数不应该有太大的计算量，否则会降低查找效率。冲突极少，函数值即哈希地址应该分布均匀。关键字集合中的任一关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此函数为均匀的哈希函数，这样才能保证存储空间的有效利用，从而减少冲突。

89.3.2.构造哈希函数的方法对数字的关键字可有下列构造方法:若是非数字关键字，则需先对其进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法

9哈希函数为关键字的线性函数H(key)=key或者H(key)=a?key+b1.直接定址法此法仅适合于：地址集合的大小==关键字集合的大小由于直接定址所得地址集合和关键字集合的大小相同，因此，对于不同的关键字不会发生冲突，但实际中使用这种哈希函数的情况很少。

10例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为:H（key）=key+（-1948）这样就可以方便地存储和查找1948年后任一年的记录。地址年份人数011949．．．．．．．．．．．．．．．．．．221970

112.数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8