93 哈希查找931 什么是哈希表查找效率由比较一次缩小的查.ppt

哈希查找
什么是哈希表
查找效率由比较一次缩小的查找范围决定。
顺序查找是对无序集的查找,关键字比较的结果为“=”或“≠”两种可能,其平均时间为O(n)。
而二分法查找和各种树表的查找是对有序集的查找,关键字比较的结果为“>”、“=”、“<”三种可能,其查找速度较快,平均时间为O(log2n)。
要想提高查找的效率,就不能只是依赖于比较进行查找。理想的情况是依据关键字直接得到其对应的数据元素位置,即要求关键字与数据元素间存在一一对应关系,通过这个关系,能很快地由关键字得到对应的数据元素位置,其查找的时间期望值为O(1)。
基本思想:在记录的存储地址和它的关键字之间建立一个确定的对应关系;这样,不经过比较,一次存取就能得到所查元素的查找方法
定义
哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~
哈希函数是一种映象,是从关键字空间到存储地址空间的一种映象
哈希函数可写成:addr(ai)=H(ki)
ai是表中的一个元素
addr(ai)是ai的存储地址
ki是ai的关键字
关键字
集合
存储地址
集合
hash
哈希表——应用哈希函数,由记录的关键字确定记录在表中的地址,并将记录放入此地址,这样构成的表叫~
哈希查找——又叫散列查找,利用哈希函数进行查找的过程叫~
例 30个地区的各民族人口统计表
编号地区别总人口汉族回族…...
1 北京
2 上海
…...
…...
以编号作关键字,
构造哈希函数:H(key)=key
H(1)=1
H(2)=2
以地区别作关键字,取地区
名称第一个拼音字母的序号
作哈希函数:H(Beijing)=2
H(Shanghai)=19
H(Shenyang)=19
例 11个元素的关键字分别为 18,27,1,20,22,6,10,13,41,15,25。选取关键字与元素位置间的函数为 f1(key)=key mod 11,则元素存放在如下的哈希表中:
0
1
2
3
4
5
6
7
8
9
10
22
1
13
25
15
27
6
18
41
20
10
例已知线性表的关键字集合为S={and,begin,do,end,for,go ,if,repeat,then,until,while}
设哈希表存放在以为数组HT[26]中。
取哈希函数f2(key)为关键字中第一个字母在字母表{a,b,…,z}中的序号(序号范围是0~25)即:
f2(key)=ASC(key[0])-ASC(“a”)
其中设key的类型为长度为8的字符数组。则构造的哈希表如下图所示。
哈希地址
关键字
0
and
…
4
end
…
17
repeat
…
20
until
…
25
例若在上例的集合S中增加4个关键字构成集合S1=S+{else,array,with,up},此时仍可使用里上例中的一维数组来存放S1的哈希表。 但却不宜使用f2来作为S2的哈希函数,这是因为对于不同的两个关键字,由f2得到的哈希地址可能相同。如f2(else)= f2(end),这表示要在HT[4]上填入关键字不等的两个结点,显然这是不合理的。通过分析,我们可取S2的哈希函数f3(key)的值为:key中首尾字母在字母表中序号的平均值。
从例子可见:
哈希函数只是一种映象,所以哈希函数的设定很灵活,只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。
在一般情况下,散列表的空间必须比结点集合的空间大,这样虽然浪费了一些空间,但却可提高查找的效率。假设散列表的空间大小为m,装入哈希表中的结点数是n,则称α=n/m为哈希表的装填因子。在使用时,一般取α=~。
冲突:key1key2,但H(key1)=H(key2)的现象叫~。哈希函数通常是一种压缩映象,所以冲突不可避免,只能尽量减少;同时,冲突发生后,应该有处理冲突的方法
所以,哈希方法需要解决以下两个问题:
①构造好的哈希函数
②制定解决冲突的方案。
哈希函数的构造方法
直接定址法
构造:取关键字或关键字的某个线性函数作哈希地址,即H(key)=key 或 H(key)=a·key+b
特点
直接定址法所得地址集合与关键字集合大小相等,不会发生冲突
实际中能用这种哈希函数的情况很少
例关键字集合为{100,300,500,700,800,900},选取哈希函数为: Hash(key)=key/100
则在哈希表中存放如下:
0
1
2
3
4
5
6
7
8
9
100
300
500
700
800
900
数字选择法
构造:如果事先知道关键字的