数据结构课件第9章查找1章节幻灯片.ppt

4.2 哈希函数的构造方法 4.2.1 直接定址法 4.2.2 数字分析法 4.2.3 平方取中法 4.2.4 折叠法 4.2.5 除留余数法 4.2.6 伪随机数法 4.2.1 直接定址法 哈希函数为关键字的线性函数： H(key) = key 或者 H(key) = a * key + b 其中a和b为常数 此法仅适合于： 地址集合的大小 == 关键字集合的大小 4.2.2 数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成。 分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。 此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。 4.2.2 数字分析法(举例) 例 有80个记录，关键字为8位十进制数， 哈希地址为2位十进制数 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. ….. ?? ? ??? ?? 分析： ?只取8 ?只取1 ?只取3、4 ?只取2、7、5 ????数字分布近乎随机 所以：取????任意两位或两位 与另两位的叠加作哈希地址 4.2.3 平方取中法 以关键字的平方值的中间几位作为存储地址。 求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 4.2.4 折叠法 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。此法适于关键字的数字位数特别多的情况。有两种叠加处理的方法： 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 4.2.4 折叠法(举例) 例如，关键字为 ：0442205864，哈希地址位数为4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 间界叠加 4.2.5 除留余数法(取模法) 设定哈希函数为: H(key) = key MOD p ( p≤m ) 其中， m为表长 4.2.6 伪随机数法 H(x) = (a * x + b) mod p 其中， a, b, p都是常数。 4.3 处理冲突的方法 “处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。处理冲突的方法有： 4.3.1 开放定址法 4.3.2 再哈希法 4.3.3 链地址法 4.3.1 开放定址法 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤s≤m-1 Hi = ( H(key) + di ) MOD m 其中： i=1, 2, …, s H(key)为哈希函数;m为哈希表长; di为增量序列,有下列三种取法: 4.3.1 开放定址法(续) 1) 线性探测再散列 di = c? i 最简单的情况 c=1 2) 二次探测再散列 di = 12, -12, 22, -22, …, 3) 随机探测再散列 di 是一组伪随机数列 或者 di=i×H2(key) (又称双散列函数探测) 4.3.2 再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，直到冲突不再发生。 即：Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的哈希函数 特点：计算时间增加 4.3.3 链地址法 能够映射到同一个地址的所有元素形成一个链表 在查找过程中，先找到该地址，然后在该地址确定的链表中查找 4.4 哈希表的查找 给定k值 计算H(k) 此地址为空 关键字==k 查找失败 查找成功 按处理冲突 方法计算Hi Y N Y N 对于给定值 K, 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 否则 “求下一地址 Hi” ， 直至r[Hi] = NULL (查找不成功) 或r[Hi].key = K (查找成功) 为止。 4.5 哈希表的插入 例如: