1、 一、一、哈希表是什么？哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法 三、处理冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找9.3 哈哈 希希 表表 以上两节讨论的表示查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关关键字键字之间不存在不存在一个确定的关系，一、哈希表是什么？哈希表是什么？ 查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较， 查找的效率查找的效率取决于和给定值进行比较进行比较的关键字个数个数。 只有一个办法：预先知道所查关键字在表中的位置， 对于频繁使用的查找表，希望 ASL = 0。 即要求：记录在表中位置和其
2、关键字之间存在一种确定的关系。若以下标为以下标为000 999 的顺序表的顺序表表示之。例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：对于如下
3、 9 个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3ChenZhaoQianSunLiWuHanYeDei问题问题: 若添加关键字 Zhou , 怎么办？怎么办？能否找到能否找到另一个哈希函数？1) 哈希函数是一个映象映象，即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活灵活，只要这个地址集地址集合的 大小不超出允许范围不超出允许范围即可；从这个例子可见：从这个例子可见：2) 由于哈希函数是一个压缩映象压缩映象，因此
4、，在一般情况下，很容易产生“冲突冲突”现象，即： key1 key2，而 f(key1) = f(key2)。3) 很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。哈希表的定义： 根据设定的哈希函数哈希函数 H(key) 和所选中的处处理冲突的方法理冲突的方法，将一组关键字映象到映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置存储位置，如此构造所得的查找表称
5、之为“哈希表哈希表”或“散列表散列表”。这一映象过程称为“哈希造表哈希造表”或“散列散列”。所得存储地址称为“哈希地址哈希地址”或“散列地址散列地址”。二、构造哈希函数的方法构造哈希函数的方法 对数字数字的关键字可有下列构造方法： 若是非数字关键字非数字关键字，则需先需先对其进行进行数字化处理数字化处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b1. 直接定址法直接定址法此法仅适合于：此法仅适合于：
6、地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小2. 除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key) = key MOD p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子 给定一组关键字为：12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3例如：例如：为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质则所有含质因子因子 3 的关键字均映射到的关键字均映射到“3 的
7、倍数的倍数”的的地址上地址上，从而增加了“冲突”的可能。 实际造表时，采用何种采用何种构造哈希函数的方法方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到的原则是使产生冲突的可能性降到尽可能地小尽可能地小。三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址。1. 开放定址法开放定址法2. 再哈希法再哈希法3. 链地址法（不讲）链地址法（不讲） 为产生冲突的地址 H(key) 求得一个地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：H0 = H(key) Hi =
8、 ( H(key) + di ) MOD m i=1, 2, , s1. 开放定址法开放定址法对增量 di 有三种取法：o1) 线性探测再散列线性探测再散列 di = c i 最简单的情况 c=1o2) 平方探测再散列平方探测再散列 di = 12, -12, 22, -22, , ,o3) 随机探测再散列随机探测再散列 di 是一组伪随机数列伪随机数列 注意：注意：增量增量 di 应具有应具有“完备性完备性”例如例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 0 1 2 3
9、 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10190123 145568190123 1468若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突11 8236551182361 1 2 1 3 6 2 5 11 1 2 1 2 1 4 1 3两种方法的平均查找长度：o 线性探测再散列：n ASL(9)=1/9(14+22+3+5+6)=22/9o 二次探测再散列：n ASL(9)=1/9(15+22+3+4)=16/9o1) 选用的哈希函数哈希函数；o2) 选用的处理冲突的方法处理冲突的方法；o3) 哈希表饱和的程度，装载因子装载
10、因子 =n/m 值的大小大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析: 从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。哈希表的平均查找长度 利用装填因子所计算的平均查找长度是近似值！o 线性探测再散列哈希表：o 二次探测再散列、随即探测再散列哈希表： 11121nlS1ln1nrS2. 再哈希法再哈希法oHi=RHi(key) i=1,2,.k RHi是不同的哈希函数，当产生地址是不同的哈希函数，当产生地址冲突时计算另一个哈希函数地址，直冲突时计算另一个哈希函数地址，直到冲突不再发生。到冲突不再发
11、生。这种方法不易产生这种方法不易产生“聚集聚集”，但增加了，但增加了计算时间。计算时间。课堂习题o 设有一个按各元素的值排好序的线性表且长度大于2，对给定的值K，分别用顺序查找法和折半查找法查找一个与K相等的元素，比较次数分别是s和b；在查找不成功的情况下，正确的s和b的数量关系是（ ）。A. 总有s=bB. 总有sbC. 总有sbD. 与K值大小有关答案：Bo 对有18个元素的有序表A作二分（折半）查找，则查找A3的比较序列的下标为（）A. 1,2,3B. 9,5,2,3C. 9,5,3D. 9,4,2,3答案：Do设散列表长m=14，散列函数为h(k)=k%11,表中已有4个记录，如果用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是（）。A. 8B. 3C. 5D. 9 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 315 386184答案：Do 在采用线性探测法处理冲突时，假定装填因子值为0.5，则查找任一元素的平均查找长度为（）。A. 1B. 1.5C. 2D. 2.5答案：Bo 设散列函数为H(k)=k%7,一组关键字为23，14，9，6，30，12和18。散列表的地址空间为06，分别用线性探测法和二次探测法解决冲突，依次将这组关键字插入表中，则得到的散列表为（），平均查找长度分别为（）。
