计算机软件基础
4.4 哈希查找
思考：分析前面介绍过的各种查找方法的共同点，考虑是否有突破常规的高效率查找方法？
提示：在元素的存放位置上动动脑筋，
使查找效率大大提高。
计算机软件基础一,哈希表的概念及建立
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,是如何在冲突出现时正确地处理冲突。
计算机软件基础
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
哈希地址表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62 30 18
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 62 30 18
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 78 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 48 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
18 62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 18 62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 18 62 30 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 78 18 62 30 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 18 62 30 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 18 62 30 32 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 18 62 30 32 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 48 18 62 30 32 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表计算机软件基础
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 48 62 30 18 21
线性探测处理冲突生成的哈希表
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 48 18 62 30 32 21
二次探测处理冲突生成的哈希表计算机软件基础
66
78 45
48
18 62
30
2132
1
3
2
9
10
6
7
8
4
5
0
54
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
链地址法处理冲突生成的哈希表计算机软件基础思考,一旦按照某种处理冲突的方法生成了哈希表，如何在此哈希表上实现指定关键字值元素的查找？
解决方法,哈希查找的过程实质上就是按照建立哈希表时处理冲突的方法，
根据哈希地址在哈希表上查找指定关键字的元素。由于冲突的存在，在哈希查找过程中对关键字的比较次数可能不只一次。
计算例题中分别采用三种不同方法处理冲突进行哈希查找的平均查找长度。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 48 62 30 18 21
线性探测处理冲突生成的哈希表关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表
n
i
iicpA S L
1
= (1+1+3+1+1+2+1+5+6+2)/10 = 2.3
计算例题中分别采用三种不同方法处理冲突进行哈希查找的平均查找长度。
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表
n
i
iicpA S L
1
= (1+1+3+1+1+2+1+3+4+1)/10 = 1.8
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 48 18 62 30 32 21
二次探测处理冲突生成的哈希表计算例题中分别采用三种不同方法处理冲突进行哈希查找的平均查找长度。
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表
n
i
iicpA S L
1
= (1+1+2+1+1+2+1+1+2+3) /10 = 1.5
66
78 45
48
18 62
30
2132
1
3
2
9
10
6
7
8
4
5
0
54
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
链地址法处理冲突生成的哈希表计算机软件基础三,哈希查找
算法前提：
1.除留余数法作为哈希函数 hash (k) = k % p;
2,用线性探测再散列处理冲突 ;
3.哈希表已经建好（哈希表空间为 0 ~ m-1）
算法一：
计算机软件基础
算法：
int hash(int k)
/*哈希函数,返回值为计算出的哈希地址 */
{int h;
h=k%p; /*p为一个常数 */
return h;
} /*hash*/
int hashsearch1( ElemType ht[],int k)
/*在哈希表 ht[m]上查找关键字为 k的元素 */
{int h,i; /*m为一个常数 */
h=hash(k); /*h用于存放哈希地址 */
i=0;
计算机软件基础
while((i<m)&&(ht[h].key!=k))
{i++;
h=(h+1)%m; /*线性探测进行查找 */
}
if(i<m) return(h);
/*若查找成功,返回元素所在的位置 */
else return(-1);
/*若查找失败,则返回 -1*/
} /*hashsearch1*/
计算机软件基础算法二：
算法前提：
1.除留余数法作为哈希函数 hash (k) = k % p;
2,用链地址法处理冲突 ;
3.哈希表已经建好（哈希表空间为 0 ~ m-1）；
4,hash函数的说明同上一算法（在此略去）
计算机软件基础
算法：
struct chain {
ElemType data;
struct chain *next;
};
struct chain *hashsearch2 (struct chain *ht[],
int k)
/*在哈希表 ht[m]上查找关键字为 k的元素 */
{struct chain *q;
q=ht[hash(k)];
/*选定查找关键字对应哈希地址的单链表 */
计算机软件基础
while((q!=NULL)&&(q->data.key!=k))
/*在该单链表上从前向后顺序查找 */
q=q->next;
return(q);
/*若查找成功,返回所查找元素的指针；若失败,则返回空指针 */
} /*hashsearch2*/
4.4 哈希查找
思考：分析前面介绍过的各种查找方法的共同点，考虑是否有突破常规的高效率查找方法？
提示：在元素的存放位置上动动脑筋，
使查找效率大大提高。
计算机软件基础一,哈希表的概念及建立
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,是如何在冲突出现时正确地处理冲突。
计算机软件基础
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
哈希地址表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62 30 18
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 62 30 18
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 78 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
① 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用线性探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 48 62 30 18 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
18 62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 18 62 30
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 18 62 30 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
45 78 18 62 30 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 18 62 30 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 18 62 30 32 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 18 62 30 32 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表
② 对关键字序列（ 62,30,18,45,21,78，
66,32,54,48）,用二次探测再散列处理冲突生成对应的哈希表。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 48 18 62 30 32 21
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表生成的哈希表计算机软件基础
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 48 62 30 18 21
线性探测处理冲突生成的哈希表
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 48 18 62 30 32 21
二次探测处理冲突生成的哈希表计算机软件基础
66
78 45
48
18 62
30
2132
1
3
2
9
10
6
7
8
4
5
0
54
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
链地址法处理冲突生成的哈希表计算机软件基础思考,一旦按照某种处理冲突的方法生成了哈希表，如何在此哈希表上实现指定关键字值元素的查找？
解决方法,哈希查找的过程实质上就是按照建立哈希表时处理冲突的方法，
根据哈希地址在哈希表上查找指定关键字的元素。由于冲突的存在，在哈希查找过程中对关键字的比较次数可能不只一次。
计算例题中分别采用三种不同方法处理冲突进行哈希查找的平均查找长度。
0 1 2 3 4 5 6 7 8 9 10
66 45 78 32 54 48 62 30 18 21
线性探测处理冲突生成的哈希表关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表
n
i
iicpA S L
1
= (1+1+3+1+1+2+1+5+6+2)/10 = 2.3
计算例题中分别采用三种不同方法处理冲突进行哈希查找的平均查找长度。
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表
n
i
iicpA S L
1
= (1+1+3+1+1+2+1+3+4+1)/10 = 1.8
0 1 2 3 4 5 6 7 8 9 10
66 45 78 54 48 18 62 30 32 21
二次探测处理冲突生成的哈希表计算例题中分别采用三种不同方法处理冲突进行哈希查找的平均查找长度。
关键字
62 30 18 45 21 78 66 32 54 48
地址 7 8 7 1 10 1 0 10 10 4
哈希地址表
n
i
iicpA S L
1
= (1+1+2+1+1+2+1+1+2+3) /10 = 1.5
66
78 45
48
18 62
30
2132
1
3
2
9
10
6
7
8
4
5
0
54
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
链地址法处理冲突生成的哈希表计算机软件基础三,哈希查找
算法前提：
1.除留余数法作为哈希函数 hash (k) = k % p;
2,用线性探测再散列处理冲突 ;
3.哈希表已经建好（哈希表空间为 0 ~ m-1）
算法一：
计算机软件基础
算法：
int hash(int k)
/*哈希函数,返回值为计算出的哈希地址 */
{int h;
h=k%p; /*p为一个常数 */
return h;
} /*hash*/
int hashsearch1( ElemType ht[],int k)
/*在哈希表 ht[m]上查找关键字为 k的元素 */
{int h,i; /*m为一个常数 */
h=hash(k); /*h用于存放哈希地址 */
i=0;
计算机软件基础
while((i<m)&&(ht[h].key!=k))
{i++;
h=(h+1)%m; /*线性探测进行查找 */
}
if(i<m) return(h);
/*若查找成功,返回元素所在的位置 */
else return(-1);
/*若查找失败,则返回 -1*/
} /*hashsearch1*/
计算机软件基础算法二：
算法前提：
1.除留余数法作为哈希函数 hash (k) = k % p;
2,用链地址法处理冲突 ;
3.哈希表已经建好（哈希表空间为 0 ~ m-1）；
4,hash函数的说明同上一算法（在此略去）
计算机软件基础
算法：
struct chain {
ElemType data;
struct chain *next;
};
struct chain *hashsearch2 (struct chain *ht[],
int k)
/*在哈希表 ht[m]上查找关键字为 k的元素 */
{struct chain *q;
q=ht[hash(k)];
/*选定查找关键字对应哈希地址的单链表 */
计算机软件基础
while((q!=NULL)&&(q->data.key!=k))
/*在该单链表上从前向后顺序查找 */
q=q->next;
return(q);
/*若查找成功,返回所查找元素的指针；若失败,则返回空指针 */
} /*hashsearch2*/
