数据结构精品课件-哈希函数中处理冲突的方法.pptVIP

第八章 查找 8.1 查找的基本概念 8.3 基于树的查找法 8.5 总结与提高 8.2 基于线性表的查找法 8.4 计算式查找---哈希法 8.4 计算式查找---哈希法 一、哈希表的定义 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希法性能分析 为产生冲突的关键字寻找下一个哈希地址。 1. 开放定址法 2. 链地址法 除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。其含义是： 3. 建立公共溢出区 三、处理冲突的方法 为产生冲突的关键字 H(key) 求得一个探测地址序列(在其中逐个探测空哈希地址)： H0, H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m di 为探测增量有三种，i=1, 2, …, m-1 1. 开放定址法 (1) 线性探测再散列 di = c? i 最简单的情况 c=1 (2) 平方探测再散列 di = 12, -12, 22, -22, …, (3) 随机探测再散列 di 是一组伪随机数列 或者 di=i×H2(key) (又称双散列函数探测) 探测增量序列 di 的三种取法： 即：产生的 Hi 均不相同, 且m-1 个Hi 值能覆盖 哈希表中所有地址。则要求： 注意：增量 di 应具有“完备性” ※ 随机探测时的 m 和 di 应没有公因子； ※ 平方探测时的表长 m 应为形如 4j+3 的素数 （如: 7, 11, 19, 23, … 等）； ※ 避免二次聚集。 0 1 2 3 4 5 6 7 8 9 10 例如哈希表长m=11，现 有关键字集合： { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 19 01 23 14 55 68 (1)采用线性探测再散列处理冲突 11 82 36 1 1 2 1 3 6 2 5 1 0 1 2 3 4 5 6 7 8 9 10 19 01 23 14 68 (2)采用二次探测再散列处理冲突 55 11 82 36 1 1 2 1 2 1 4 1 2 ASL=22/9 ASL=15/9 设：H2(key)=(3 key) MOD 10 + 1 di=i×H2(key) 19 01 23 14 55 68 11 82 36 2 1 1 1 2 1 2 1 3 ASL=14/9 0 1 2 3 4 5 6 7 8 9 10 (3)采用双散列函数探测 线性探测处理冲突时： ASL = 双散列探测处理冲突时：ASL = 22/9 14/9 二次探测处理冲突时： ASL = 15/9 本例不同的处理冲突方法的ASL为： { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 将所有哈希地址相同的记录 都链接在同一链表中。 36 82 68 ? ? ? ? ? ? 14 01 23 11 19 55 0 1 2 3 4 5 6 ? ASL=(6×1+2×2+3)/9=13/9 设哈希函数为： H(key)=key MOD 7 显然不会发生二次聚集 2. 链地址法： { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 按哈希函数的值域的范围设立向量为基本表,另设立同样大小的向量为公共溢出区,将所有发生冲突的记录都顺序存放在公共溢出区中。