软件工程与c语言chapter4.4.ppt

计算机软件基础
哈希查找
思考:分析前面介绍过的各种查找方法的共同点,考虑是否有突破常规的高效率查找方法?
提示:在元素的存放位置上动动脑筋,使查找效率大大提高。
计算机软件基础
一. 哈希表的概念及建立
1. 哈希表的有关概念
(1)哈希函数
哈希函数是指对于线性表中各个元素所建立的关键字值与其在一维数组中存放位置之间的函数(对应关系),其形式为:
addr(ai) = H(ki)
其中,H为哈希函数名,ai为线性表中的第i个元素,ki为第i个元素的关键字值。
计算机软件基础
(2)哈希地址
通过哈希函数,对线性表中的每个元素根据其关键字值所计算出的在一维数组中的存放位置称为该元素的哈希地址。
(3)哈希表
按哈希地址存放每个元素所生成的顺序表称作哈希表。哈希表空间的单元数应大于元素的个数。
计算机软件基础
例:若有一线性表的关键字集合为{65,47,86,34,12,77},对其构造的哈希函数为:H(k) = k/10,若所开辟的哈希表空间地址范围为0—9,则形成的哈希表如下所示:
地址
0
1
2
3
4
5
6
7
8
9
关键字值
12
34
47
65
77
86
思考:若还存在关键字为69的元素,在生成哈希表的过程中会有什么麻烦,有什么办法能解决?
计算机软件基础
(4)冲突
在计算哈希地址时所出现的不同关键字对应到同一地址的现象,称为冲突。
处理冲突中的两个关键问题:
1. 如何构造合适的哈希函数以使冲突降低到最少程度;
2. 是如何在冲突出现时正确地处理冲突。
计算机软件基础

(1)直接定址法
取关键字值本身或其线性函数值作为哈希地址。其形式为:H(k) = a×k+b,其中a和b为常数。
(2)数字分析法
取关键字中分布较均匀的n个数位作为哈希地址(n的值应为哈希表的地址位数)。
计算机软件基础
(3)平方取中法
取关键字平方后的中间几位作为哈希地址,是对数字分析法的改进方法。
(4)除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得的余数作为哈希地址,其形式为:H(k) = k % p。一般情况下,可以选p为不大于m的最大质数。
计算机软件基础
二. 冲突的处理方法
1. 开放定址法
基本思想:若在某个地址处发生了冲突,则沿着一个特定的探测序列在哈希表中探测下一个空单元,一旦找到,则将新元素存入此单元中。其探测的序列可用下式描述:
Hi = ( H(k) + di ) % m (i = 1,2,3,…)
(1)当di取1,2,3,…,m –1时,称为线性探测再散列;
(2)当di取12,–12,22,–22, 32,–32,…,±j2(j≤m/2)时,称为二次探测再散列。
计算机软件基础
2. 链地址法
基本思想:为每个哈希地址建立一个单链表,将所有哈希地址相同的元素存储在同一单链表中,单链表的头指针存放在基本表中。在将某个关键字的结点向单链表中插入时,既可以插在链尾上,也可以插在链头上。
计算机软件基础
例:设有关键字序列(62,30,18,45,21,78,66,32,54,48),现用除留余数法作为哈希函数,分别用①线性探测再散列、②二次探测再散列处理冲突、③链地址法处理冲突,画出所生成的哈希表。
关键字
62
30
18
45
21
78
66
32
54
48
地址
7
8
7
1
10
1
0
10
10
4
哈希地址表