1
9.4 哈希查找表
一,哈希表的概念
二,哈希函数的构造方法
三、哈希 冲突 处理方法
四,哈希表的查找及分析
2
一、哈希表的概念
哈希表,也称作散列存储结构。
散列法存储的基本思想,建立 关键码字 与其 存储位置 的 对应
关系,或者说，由关键码的 值 决定数据的存储 地址 。
优点,查找速度极快（ O(1)）,查找效率与元素个数 n无关！
例 1,若将学生信息按如下方式存入计算机，如：
将 2001011810201的所有信息存入 V[01]单元；
将 2001011810202的所有信息存入 V[02]单元；
……
将 2001011810231的所有信息存入 V[31]单元。
欲查找学号为 2001011810216的信息，便可直接访问 V[16]！
3
例 2, 有数据元素序列 (14,23,39,9,25,11),若规定
每个元素 k的存储地址 H（ k） ＝ k,请画出存储结构图 。
解,根据散列函数 H（ k）＝ k,可知元素 14应当存入地址
为 14的单元，元素 23应当存入地址为 23的单元,……,
对应散列存储表（哈希表）如下：
讨论：如何进行散列查找？
根据存储时用到的散列函数 H(k)表达式,迅即可查到结果！
例如，查找 key=9,则访问 H(9)=9号地址，若内容为 9则成功；
若查不到，应当设法返回一个特殊值，例如空指针或空记录。
地址 … 9 … 11 … 14 … 23 24 25 … 39 …
内容 14119 23 25 39
明显缺点：空间效率低 如何解决？
H(k)称为散列函数
4
选取某个函数，依该函数 按关键字计算元素的存储位置
并按此存放；查找时也 由同一个函数 对给定值 k计算地址,
将 k与地址中内容进行比较，确定查找是否成功。
通常关键码的集合比哈希地址集合大得多，因而经
过哈希函数变换后,可能将不同的关键码映射到同
一个哈希地址上,这种现象称为 冲突 。
Hash查找法
哈希方法
(杂凑法 )
哈希函数
(杂凑函数 )
哈希表
(杂凑表 )
冲 突
哈希方法中使用的转换函数称为 哈希函数 (杂
凑函数 )
按上述思想构造的表称为 哈希表 (杂凑表 )
若干术语
5
有 6个元素的关键码分别为,（ 14,23,39,9,25,11） 。
选取关键码与元素位置间的函数为 H(k)=k mod 7
通过哈希函数对 6个元素建立哈希表：
25
3923
9
14
冲突现象举例：
6个元素用 7个
地址应该足够 !
H(14)=14%7=0 11 H(25)=25%7=4
H(11)=11%7=4
有冲突！
0 1 2 3 4 5 6
6
所以, 哈希方法必须解决以下两个问题：
1） 构造好的哈希函数
（ a）所选函数尽可能 简单,以便提高转换速度；
（ b）所选函数对关键码计算出的地址，应在哈希地址内集
中并大致 均匀 分布，以减少空间浪费。
2）制定一个好的解决冲突的方案
查找时, 如果从哈希函数计算出的地址中查不到关键码, 则
应当依据解决冲突的规则, 有规律地查询其它 相关单元 。
在哈希查找方法中，冲突是不可能避免的，只能
尽可能减少。
7
二,哈希函数的构造方法
常用的哈希函数构造方法有：
1,直接定址法
2,除留余数法
3,乘余取整法
4,数字分析法
5,平方取中法
要求一,n个数据原仅占用 n个地址，
虽然散列查找是以空间换时间，但仍
希望散列的地址空间尽量小。
要求二,无论用什么方法存储，目
的都是尽量均匀地存放元素，以避免
冲突。
8
Hash(key) = a·key + b (a,b为常数 )
优点,以关键码 key的某个线性函数值为哈希地址，
不会产生冲突,
缺点,要占用连续地址空间，空间效率低。
例,关键码集合为 {100,300,500,700,800,900}，
选取哈希函数为 Hash(key)=key/100，
则存储结构 （ 哈希表 ） 如下：
0 1 2 3 4 5 6 7 8 9
900800700500300100
1、直接定址法
9
Hash(key)= ? B*( A*key mod 1 ) ?
(A,B均为常数, 且 0<A<1,B为整数 )
特点,以关键码 key乘以 A,取其小数部分, 然后
再放大 B倍并 取整, 作为哈希地址 。
Hash(key)=key mod m (m是一个整数 )
特点,以关键码除以 p的余数作为哈希地址。
关键,如何选取合适的 m？
技巧,若设计的哈希表长为 m，则一般取 p≤m且为 质数
（也可以是合数，但不能包含小于 20的质因子）。
3、乘余取整法
2、除留余数法
（ A*key mod 1）
就是取 A*key 的
小数部分
例,欲以学号最后两位作为地址，则哈希函数应为：
H(k)=100*(0.01*k % 1 )
其实也可以用法 2实现,H(k)=k % 100
10
特点,选用关键字的某几位组合成哈希地址。选用原则应
当是：各种符号在该位上出现的频率大致相同。
3 4 7 0 5 2 4
3 4 9 1 4 8 7
3 4 8 2 6 9 6
3 4 8 5 2 7 0
3 4 8 6 3 0 5
3 4 9 8 0 5 8
3 4 7 9 6 7 1
3 4 7 3 9 1 9
例,有一组（例如 80个）关键码，其样式如下：
4、数字分析法
讨论：
① 第 1,2位均是, 3和 4”，第 3位也
只有, 7,8,9”，因此，这几位不
能用,余下四位分布较均匀,可作
为哈希地址选用。
位号,① ② ③ ④ ⑤ ⑥ ⑦
② 若哈希地址取两位（因元素仅 80
个），则可取这四位中的任意两位组
合成哈希地址，也可以取其中两位与
其它两位叠加求和后，取低两位作哈
希地址。
11
特点,对关键码平方后，按哈希表大小，取中间的若干位
作为哈希地址。
理由,因为中间几位与数据的每一位都相关。
例,2589的平方值为 6702921，可以取中间的 029为地址。
6、折叠法
特点,将关键码自左到右分成位数相等的几部分 （ 最后一部
分位数可以短些 ）, 然后将这几部分叠加求和, 并按
哈希表表长, 取后几位作为哈希地址 。
适用于,每一位上各符号出现概率大致相同的情况 。
法 1,移位法 ── 将各部分的最后一位对齐相加 。
法 2,间界叠加法 ── 从一端向另一端沿分割界来回折叠后
，最后一位对齐相加。
例, 元素 42751896,用 法 1,427＋ 518＋ 96=1041
用 法 2,427 518 96— > 724+518+69 =1311
5、平方取中法
12
Hash(key) = random ( key ) (random为伪随机函数 )
适用于,关键字长度不等的情况。造表和查找都很方便。
① 执行速度（即计算哈希函数所需时间）；
② 关键字的长度；
③ 哈希表的大小；
④ 关键字的分布情况；
⑤ 查找频率。
小结：构造哈希函数的原则：
13
三,哈希 冲突解决方法
常见的冲突处理方法有：
1.开放定址法（开地址法）
2.链地址法（拉链法）
3.再哈希法（双哈希函数法）
4.建立一个公共溢出区
14
1、开放定址法（开地址法）
设计思路,有冲突时就去寻找下一个空的哈希地址，
只要哈希表足够大，空的哈希地址总能找
到，并将数据元素存入。
具体实现：
Hi=(Hash(k)+di) mod m ( 1≤i < m )
其中：
Hash(k)为哈希函数
m为哈希表长度
di 为增量序列 1,2,… m-1,且 di=i
（ 1）线性探测法
含义：一旦冲突，就找附近（下一个）空地址存入。
15
关键码集为 {47,7,29,11,16,92,22,8,3}，
设,哈希表表长为 m=11；
哈希函数为 Hash(key)=key mod 11；
拟用 线性探测法 处理冲突 。 建哈希表如下：
解释：
① 47,7是由哈希函数得到的没有冲突的哈希地址；
0 1 2 3 4 5 6 7 8 9 10
47 7
△ ▲ △ △
例：
2911 169222 83
② Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希
地址：由 H1=(Hash(29)+1) mod 11=8,哈希地址 8为空，因
此将 29存入。
③ 另外,22,8,3同样在哈希地址上有冲突，也是由 H1找
到空的哈希地址的。
其中 3 还连续移动了 两次 （二次聚集）
16
线性探测法的优点,只要哈希表未被填满，保证能
找到一个空地址单元存放有冲突的元素；
线性探测法的缺点,可能使第 i个哈希地址的同义词
存入第 i+1个哈希地址，这样本应存入第 i+1个
哈希地址的元素变成了第 i+2个哈希地址的同
义词,……,
因此，可能出现很多元素在相邻的哈希地址
上, 堆积, 起来，大大降低了查找效率。
解决方案,可采用 二次探测法 或 伪随机探测法,以
改善, 堆积, 问题。
讨论：
17
仍举上例，改用二次探测法处理冲突，建表如下：
0 1 2 3 4 5 6 7 8 9 10
11 22 3 47 92 16 7 29 8
△ ▲ △ △
注,只有 3这个关键码的冲突处理与上例不同,
Hash(3)=3,哈希地址上冲突, 由
H1=(Hash(3)+12) mod 11=4,仍然冲突；
H2=(Hash(3)-12) mod 11=2,找到空的哈希地址，存入。
2,二次探测法
Hi=(Hash(k)± di) mod m
其中,Hash(k)为哈希函数
m为哈希表长度, m要求是某个 4k+3的质数 ；
di为增量序列 12,-12,22,-22,…, q2
3,若 di＝伪随机序列，就称为伪随机探测法
18
2、链地址法 (拉链法）
基本思想,将具有相同哈希地址的记录链成一个单链表,m个
哈希地址就设 m个单链表,然后用一个数组将 m个单
链表的表头指针存储起来，形成一个动态的结构。
设 { 47,7,29,11,16,92,22,
8,3,50,37,89 }的哈希函数为：
Hash(key)=key mod 11，
用 拉链法 处理冲突, 则建表
如右图所示 。
例,0
1
2
3
4
5
6
7
8
9
10
22 11
89
3 47
37 92
29 7
16
50
8
10
有冲突的元素可以插在表
尾,也可以插在表头。
19
3、再哈希法（双哈希函数法）
Hi=RHi(key) i=1,2,…, k
RHi均是不同的哈希函数，当产生冲突时就计算另一个
哈希函数，直到冲突不再发生。
优点,不易产生聚集；
缺点,增加了计算时间。
4,建立一个公共溢出区
思路,除设立哈希基本表外,另设立一个溢出向量表 。
所有关键字和基本表中关键字为同义词的记录，不
管它们由哈希函数得到的地址是什么，一旦发生冲突，都
填入溢出表。
20
四、哈希表的查找及分析
明确,散列函数没有, 万能, 通式（ 杂凑法）,要根据元
素集合的特性而分别构造。
讨论,哈希查找的速度是否为真正的 O（ 1）？
不是 。 由于冲突的产生, 使得哈希表的查找过程仍然要进
行比较, 仍然要以平均查找长度 ASL来衡量 。
一般地, ASL依赖于哈希表的装填因子 ?,它标志着哈希表的
装满程度 。
哈希表的长度
表中填入的记录数??
?越大，表中记录数越多，说明表装得越满，发生冲突
的可能性就越大，查找时比较次数就越多。
0≤ ?≤1
21
讨论：
2）, 冲突, 是不是特别讨厌？
答,不一定！正因为有冲突，使得文件加密后无法破译！
（单向散列函数不可逆，常用于 数字签名和间接加密 ）。
利用了哈希表性质,源文件稍稍改动，会导致哈希表变
动很大。
随机探测法）
线性探测法
拉链法）
()1ln (
1
)()
1
1
1(
2
1
(
2
1
?
?
?
?
???
?
??
??
A S L
A S L
A S L
1） 散列存储的查找效率到底是多少？
答,ASL与装填因子 ?有关！既不是严格的 O(1)，也不是 O(n)
应尽量选择一个
合适的 ?，以降低
ASL的长度
典型应用,md5散列算法
9.4 哈希查找表
一,哈希表的概念
二,哈希函数的构造方法
三、哈希 冲突 处理方法
四,哈希表的查找及分析
2
一、哈希表的概念
哈希表,也称作散列存储结构。
散列法存储的基本思想,建立 关键码字 与其 存储位置 的 对应
关系,或者说，由关键码的 值 决定数据的存储 地址 。
优点,查找速度极快（ O(1)）,查找效率与元素个数 n无关！
例 1,若将学生信息按如下方式存入计算机，如：
将 2001011810201的所有信息存入 V[01]单元；
将 2001011810202的所有信息存入 V[02]单元；
……
将 2001011810231的所有信息存入 V[31]单元。
欲查找学号为 2001011810216的信息，便可直接访问 V[16]！
3
例 2, 有数据元素序列 (14,23,39,9,25,11),若规定
每个元素 k的存储地址 H（ k） ＝ k,请画出存储结构图 。
解,根据散列函数 H（ k）＝ k,可知元素 14应当存入地址
为 14的单元，元素 23应当存入地址为 23的单元,……,
对应散列存储表（哈希表）如下：
讨论：如何进行散列查找？
根据存储时用到的散列函数 H(k)表达式,迅即可查到结果！
例如，查找 key=9,则访问 H(9)=9号地址，若内容为 9则成功；
若查不到，应当设法返回一个特殊值，例如空指针或空记录。
地址 … 9 … 11 … 14 … 23 24 25 … 39 …
内容 14119 23 25 39
明显缺点：空间效率低 如何解决？
H(k)称为散列函数
4
选取某个函数，依该函数 按关键字计算元素的存储位置
并按此存放；查找时也 由同一个函数 对给定值 k计算地址,
将 k与地址中内容进行比较，确定查找是否成功。
通常关键码的集合比哈希地址集合大得多，因而经
过哈希函数变换后,可能将不同的关键码映射到同
一个哈希地址上,这种现象称为 冲突 。
Hash查找法
哈希方法
(杂凑法 )
哈希函数
(杂凑函数 )
哈希表
(杂凑表 )
冲 突
哈希方法中使用的转换函数称为 哈希函数 (杂
凑函数 )
按上述思想构造的表称为 哈希表 (杂凑表 )
若干术语
5
有 6个元素的关键码分别为,（ 14,23,39,9,25,11） 。
选取关键码与元素位置间的函数为 H(k)=k mod 7
通过哈希函数对 6个元素建立哈希表：
25
3923
9
14
冲突现象举例：
6个元素用 7个
地址应该足够 !
H(14)=14%7=0 11 H(25)=25%7=4
H(11)=11%7=4
有冲突！
0 1 2 3 4 5 6
6
所以, 哈希方法必须解决以下两个问题：
1） 构造好的哈希函数
（ a）所选函数尽可能 简单,以便提高转换速度；
（ b）所选函数对关键码计算出的地址，应在哈希地址内集
中并大致 均匀 分布，以减少空间浪费。
2）制定一个好的解决冲突的方案
查找时, 如果从哈希函数计算出的地址中查不到关键码, 则
应当依据解决冲突的规则, 有规律地查询其它 相关单元 。
在哈希查找方法中，冲突是不可能避免的，只能
尽可能减少。
7
二,哈希函数的构造方法
常用的哈希函数构造方法有：
1,直接定址法
2,除留余数法
3,乘余取整法
4,数字分析法
5,平方取中法
要求一,n个数据原仅占用 n个地址，
虽然散列查找是以空间换时间，但仍
希望散列的地址空间尽量小。
要求二,无论用什么方法存储，目
的都是尽量均匀地存放元素，以避免
冲突。
8
Hash(key) = a·key + b (a,b为常数 )
优点,以关键码 key的某个线性函数值为哈希地址，
不会产生冲突,
缺点,要占用连续地址空间，空间效率低。
例,关键码集合为 {100,300,500,700,800,900}，
选取哈希函数为 Hash(key)=key/100，
则存储结构 （ 哈希表 ） 如下：
0 1 2 3 4 5 6 7 8 9
900800700500300100
1、直接定址法
9
Hash(key)= ? B*( A*key mod 1 ) ?
(A,B均为常数, 且 0<A<1,B为整数 )
特点,以关键码 key乘以 A,取其小数部分, 然后
再放大 B倍并 取整, 作为哈希地址 。
Hash(key)=key mod m (m是一个整数 )
特点,以关键码除以 p的余数作为哈希地址。
关键,如何选取合适的 m？
技巧,若设计的哈希表长为 m，则一般取 p≤m且为 质数
（也可以是合数，但不能包含小于 20的质因子）。
3、乘余取整法
2、除留余数法
（ A*key mod 1）
就是取 A*key 的
小数部分
例,欲以学号最后两位作为地址，则哈希函数应为：
H(k)=100*(0.01*k % 1 )
其实也可以用法 2实现,H(k)=k % 100
10
特点,选用关键字的某几位组合成哈希地址。选用原则应
当是：各种符号在该位上出现的频率大致相同。
3 4 7 0 5 2 4
3 4 9 1 4 8 7
3 4 8 2 6 9 6
3 4 8 5 2 7 0
3 4 8 6 3 0 5
3 4 9 8 0 5 8
3 4 7 9 6 7 1
3 4 7 3 9 1 9
例,有一组（例如 80个）关键码，其样式如下：
4、数字分析法
讨论：
① 第 1,2位均是, 3和 4”，第 3位也
只有, 7,8,9”，因此，这几位不
能用,余下四位分布较均匀,可作
为哈希地址选用。
位号,① ② ③ ④ ⑤ ⑥ ⑦
② 若哈希地址取两位（因元素仅 80
个），则可取这四位中的任意两位组
合成哈希地址，也可以取其中两位与
其它两位叠加求和后，取低两位作哈
希地址。
11
特点,对关键码平方后，按哈希表大小，取中间的若干位
作为哈希地址。
理由,因为中间几位与数据的每一位都相关。
例,2589的平方值为 6702921，可以取中间的 029为地址。
6、折叠法
特点,将关键码自左到右分成位数相等的几部分 （ 最后一部
分位数可以短些 ）, 然后将这几部分叠加求和, 并按
哈希表表长, 取后几位作为哈希地址 。
适用于,每一位上各符号出现概率大致相同的情况 。
法 1,移位法 ── 将各部分的最后一位对齐相加 。
法 2,间界叠加法 ── 从一端向另一端沿分割界来回折叠后
，最后一位对齐相加。
例, 元素 42751896,用 法 1,427＋ 518＋ 96=1041
用 法 2,427 518 96— > 724+518+69 =1311
5、平方取中法
12
Hash(key) = random ( key ) (random为伪随机函数 )
适用于,关键字长度不等的情况。造表和查找都很方便。
① 执行速度（即计算哈希函数所需时间）；
② 关键字的长度；
③ 哈希表的大小；
④ 关键字的分布情况；
⑤ 查找频率。
小结：构造哈希函数的原则：
13
三,哈希 冲突解决方法
常见的冲突处理方法有：
1.开放定址法（开地址法）
2.链地址法（拉链法）
3.再哈希法（双哈希函数法）
4.建立一个公共溢出区
14
1、开放定址法（开地址法）
设计思路,有冲突时就去寻找下一个空的哈希地址，
只要哈希表足够大，空的哈希地址总能找
到，并将数据元素存入。
具体实现：
Hi=(Hash(k)+di) mod m ( 1≤i < m )
其中：
Hash(k)为哈希函数
m为哈希表长度
di 为增量序列 1,2,… m-1,且 di=i
（ 1）线性探测法
含义：一旦冲突，就找附近（下一个）空地址存入。
15
关键码集为 {47,7,29,11,16,92,22,8,3}，
设,哈希表表长为 m=11；
哈希函数为 Hash(key)=key mod 11；
拟用 线性探测法 处理冲突 。 建哈希表如下：
解释：
① 47,7是由哈希函数得到的没有冲突的哈希地址；
0 1 2 3 4 5 6 7 8 9 10
47 7
△ ▲ △ △
例：
2911 169222 83
② Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希
地址：由 H1=(Hash(29)+1) mod 11=8,哈希地址 8为空，因
此将 29存入。
③ 另外,22,8,3同样在哈希地址上有冲突，也是由 H1找
到空的哈希地址的。
其中 3 还连续移动了 两次 （二次聚集）
16
线性探测法的优点,只要哈希表未被填满，保证能
找到一个空地址单元存放有冲突的元素；
线性探测法的缺点,可能使第 i个哈希地址的同义词
存入第 i+1个哈希地址，这样本应存入第 i+1个
哈希地址的元素变成了第 i+2个哈希地址的同
义词,……,
因此，可能出现很多元素在相邻的哈希地址
上, 堆积, 起来，大大降低了查找效率。
解决方案,可采用 二次探测法 或 伪随机探测法,以
改善, 堆积, 问题。
讨论：
17
仍举上例，改用二次探测法处理冲突，建表如下：
0 1 2 3 4 5 6 7 8 9 10
11 22 3 47 92 16 7 29 8
△ ▲ △ △
注,只有 3这个关键码的冲突处理与上例不同,
Hash(3)=3,哈希地址上冲突, 由
H1=(Hash(3)+12) mod 11=4,仍然冲突；
H2=(Hash(3)-12) mod 11=2,找到空的哈希地址，存入。
2,二次探测法
Hi=(Hash(k)± di) mod m
其中,Hash(k)为哈希函数
m为哈希表长度, m要求是某个 4k+3的质数 ；
di为增量序列 12,-12,22,-22,…, q2
3,若 di＝伪随机序列，就称为伪随机探测法
18
2、链地址法 (拉链法）
基本思想,将具有相同哈希地址的记录链成一个单链表,m个
哈希地址就设 m个单链表,然后用一个数组将 m个单
链表的表头指针存储起来，形成一个动态的结构。
设 { 47,7,29,11,16,92,22,
8,3,50,37,89 }的哈希函数为：
Hash(key)=key mod 11，
用 拉链法 处理冲突, 则建表
如右图所示 。
例,0
1
2
3
4
5
6
7
8
9
10
22 11
89
3 47
37 92
29 7
16
50
8
10
有冲突的元素可以插在表
尾,也可以插在表头。
19
3、再哈希法（双哈希函数法）
Hi=RHi(key) i=1,2,…, k
RHi均是不同的哈希函数，当产生冲突时就计算另一个
哈希函数，直到冲突不再发生。
优点,不易产生聚集；
缺点,增加了计算时间。
4,建立一个公共溢出区
思路,除设立哈希基本表外,另设立一个溢出向量表 。
所有关键字和基本表中关键字为同义词的记录，不
管它们由哈希函数得到的地址是什么，一旦发生冲突，都
填入溢出表。
20
四、哈希表的查找及分析
明确,散列函数没有, 万能, 通式（ 杂凑法）,要根据元
素集合的特性而分别构造。
讨论,哈希查找的速度是否为真正的 O（ 1）？
不是 。 由于冲突的产生, 使得哈希表的查找过程仍然要进
行比较, 仍然要以平均查找长度 ASL来衡量 。
一般地, ASL依赖于哈希表的装填因子 ?,它标志着哈希表的
装满程度 。
哈希表的长度
表中填入的记录数??
?越大，表中记录数越多，说明表装得越满，发生冲突
的可能性就越大，查找时比较次数就越多。
0≤ ?≤1
21
讨论：
2）, 冲突, 是不是特别讨厌？
答,不一定！正因为有冲突，使得文件加密后无法破译！
（单向散列函数不可逆，常用于 数字签名和间接加密 ）。
利用了哈希表性质,源文件稍稍改动，会导致哈希表变
动很大。
随机探测法）
线性探测法
拉链法）
()1ln (
1
)()
1
1
1(
2
1
(
2
1
?
?
?
?
???
?
??
??
A S L
A S L
A S L
1） 散列存储的查找效率到底是多少？
答,ASL与装填因子 ?有关！既不是严格的 O(1)，也不是 O(n)
应尽量选择一个
合适的 ?，以降低
ASL的长度
典型应用,md5散列算法
