§9.3 哈希表
开放地址法
例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表： 0 1
11 22
2
3
4
5
6
3
7
7
8
29
9
8
10
47 92 16
§9.3 哈希表
开放地址法
选用关键字的某几位组合成哈希地址。
选用原则应当是：各种符号在该位上出现的频率大致
相同。
适于关键字位数比哈希地址位数大，且可能出现的关 键字事先知道的情况。
§9.3 哈希表
数字分析法
例：有一组（例如80个）关键码，其样式如下： 讨论： 3 4 7 0 5 2 4 ① 第1、2位均是“3和4”，第3位也只有 3 4 9 1 4 8 7 3 4 8 2 6 9 6 “ 7、8、9”，因此，这几位不能用，余 3 4 8 5 2 7 0 下四位分布较均匀，可作为哈希地址选用。 3 4 8 6 3 0 5 ② 若哈希地址取两位（因元素仅80个）， 3 4 9 8 0 5 8 则可取这四位中的任意两位组合成哈希地 3 4 7 9 6 7 1 址，也可以取其中两位与其它两位叠加求 3 4 7 3 9 1 9 和后，取低两位作哈希地址。 位号：① ② ③ ④ ⑤ ⑥ ⑦
拟用二次探测法处理冲突。建哈希表如下： Hi = ( H(K)+di ) mod m 其中di =12, -12, 22,-22,…, j2, -j2 ( j≤m/2)。
0 1
11 22
2
3
3
4
5
6
7
7
8
29
9 10
8
47 92 16
§9.3 哈希表
开放地址法
(3) 伪随机探测法
伪随机探测法对应的探查地址序列的计算公式为： Hi = ( H(K)+di ) mod m
实际的应用中，要存储的关键字集合K，相对
U来说很小，因此分配给T的大部分空间会被浪费。
§9.3 哈希表
哈希表(Hash Tables)
给定关键字，期望通过计算，即利用哈希函数
h(x)计算出关键字在表T中的位置。
§9.3 哈希表
哈希表(Hash Tables)
在直接寻址方式下，具有关 键字k的数据元素，存放在槽k中。
访问到数组的任意元素。
§9.3 哈希表
哈希表(Hash Tables)
当关键字全域比较小的时候，利用数组(直接
寻址表)是一种简单有效的技术。
§9.3 哈希表
哈希表(Hash Tables)
直接寻址技术存在的问题：
如果全域U很大，在计算机中存储大小为|U|的
一张表T就有点不实际，甚至是不可能的。
频度很高的现象。
§9.3 哈希表
折叠法
构造：将关键字分割成位数相同的几部分，然后取这几部分 的叠加和（舍去进位）做哈希地址。 移位叠加：将分割后的几部分低位对齐相加。 间界叠加：从一端沿分割界来回折叠，然后对齐相加。
适于关键字位数很多，且每一位上数字分布大致均匀情况
§9.3 哈希表
折叠法
例：关键字为：0442205864，哈希地址位数为 4。 5864 4220 04 移位叠加 10088 H(key)=0088 例：元素42751896, 移位法： 427＋518＋96=1041 5864 0224 04 间界叠加 6092 H(key)=6092
线性探测法的优点：只要哈希表未被填满，保证能找到一 个空地址单元存放有冲突的元素；
线性探测法的缺点：可能使第i个哈希地址的同义词存入第
i+1个哈希地址，这样本应存入第i+1个哈希地址的元素 变成了第i+2个哈希地址的同义词，……， 因此，可能出现很多元素在相邻的哈希地址上“堆积”起 来，大大降低了查找效率。 可采用二次探测法或伪随机探测法，以改善“堆积”问题
§9.3 哈希表
链地址法
基本思想： 将具有相同哈希地址的记录链成一个单链表，m个哈希 地址就设m个单链表，然后用一个数组将m个单链表的表头 指针存储起来，形成一个动态的结构。 优点：插入、删除方便。 缺点：占用存储空间多。
例：已知一组关键字 (19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函数为：H(key)=key MOD 13，用链地址法处理冲突。
100
2
3
300
4
5
500
6
7
8

9
700 800 900
§9.3 哈希表
直接定址法
特点：地址集合的大小 = 关键字集合的大小。 优点：以关键码 key 的某个线性函数值为哈希地址，
不会产生冲突。
缺点：要占用连续地址空间，空间效率低。
实际中能使用这种哈希函数的情况很少
§9.3 哈希表
数字分析法
武汉科技大学
Wuhan University of Science and Technology
张 凯 计算机学院 软件工程系
2011年3月12日
第9章
查找
查找的基本概念
静态查找表
动态查找表 哈希表
§9.3 哈希表
哈希表(Hash Tables)
也被称为散列表，是普通数组概念的推广。因
为可以对数组进行直接寻址，故可以在O(1)时间内
碰撞(collision)
在哈希方式下，具有关键字 k的数据元素，存放在槽h(k) 中。 其中h(x)是散列函数。
例如：对于如下 9 个关键字： {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dai}
设哈希函数 f (key) = (Ord(关键字首字母) - Ord(„A‟) + 1) / 2 0 1 2 3 4
其中di =伪随机序列
例：表长为 11 的哈希表中已填有关键字为 17，60，29 的记录， H(key)=key MOD 11，现有第 4 个记录，其关键字为 38， 按三种处理冲突的方法，将它填入表中。 0 1 2 3 4 5 6 7 8 9 10 38 38 60 17 29 38 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 (2) H(38)=38 MOD 11=5 冲突 H1=(5+1² MOD 11=6 冲突 ) H2=(5-1² MOD 11=4 不冲突 ) (3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为 9，则： H1=(5+9) MOD 11=3 不冲突
2) 由于哈希函数是一个压缩映像，因此，在一般情况下，很容 易产生“冲突”现象，即：key1 key2，而 f (key1) = f (key2)。 这种具有相同函数值的关键字称为同义词。
3) 很难找到一个不产生冲突的哈希函数。一般情况下，只能 选择恰当的哈希函数，使冲突尽可能少地产生。 因此：在构造这种特殊的“查找表”时，除了需要选择一
Han
5
6
Li
7
8
9
10
11
Wu
12
13
Zhou
问题: 若添加关键字 Zhou，会出现什么情况 ？ 从这个例子可见：
Chen Dai
Qian Sun
Zhou Ye Zhao
1) 哈希函数是一个映像，即：将关键字的集合映射到某个地址 集合上。它的设置很灵活，只要使得关键字的哈希函数值都 落在表长允许的范围之内即可；
§9.3 哈希表
直接定址法
取关键字或关键字的某个线性函数值为散列地址，即哈 希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b (其中a、b为常数) 例：关键码集合为{ 100，300，500，700，800，900 }， 选取哈希函数为 Hash(key)=key/100，画初存储结构(哈希表) 0 1
1. 直接定址法 2. 数字分析法
4. 折叠法 5. 除留余数法
3. 平方取中法
6. 随机数法
对非数字关键字，常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash， RSHash，SDBMHash，PJWHash，ELFHash等等
§9.3 哈希表
哈希函数的构造方法
§9.3 哈希表
平方取中法（较常用）
构造：以关键字的平方值的中间几位作为哈希地址。 求“关键字的平方值”的目的是“扩大差别”，同时平方 值的中 间各位又能受到整个关键字中各位的影响。
例：2589的平方值为6702921，可以取中间的029为地址。
此方法适合于：关键字中的每一位都有某些数字重复出现
§9.3 哈希表
除留余数法(最常用)
给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 11, 则他们对
应的哈希函数值将为
0 33 1 12 2 24 3 4 5 6 39 7 18 8 9 10 21
§9.3 哈希表
除留余数法(最常用)
给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 9, 则他们对应
其中，Random是伪随机函数。
通常，当关键字长度不等时采用此法构造哈希函数较恰当
§9.3 哈希表
哈希函数的构造方法
实际造表时，采用何种构造哈希函数的方法取决于建表的关 键字集合的情况（包括关键字的范围和形态），总的原则是使产 生冲突的可能性降到尽可能地小。 选取哈希函数，考虑以下因素： 1）计算哈希函数所需时间 2）关键字长度 3）哈希表长度（哈希地址范围） 4）关键字分布情况 5）记录的查找频率