哈希函数为hashkey-数据结构课程教学网站.PPT

除留余数法 设哈希表中允许的地址数为 m, 取一个不大于 m，但最接近于或等于 m 的质数 p作为除数，利用以下公式把关键字转换成哈希地址。哈希函数为： hash ( key ) = key % p p ? m 其中, “%”是整数除法取余的运算，要求这时的质数 p 不是接近2的幂。 例如: 给定一组关键字为：12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3 为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 例：有一个关键字 key = 962148，哈希表大小 m = 25，即 HT[25]。取质数 p= 23。哈希函数 hash ( key ) = key % p。则哈希地址为 可以按计算出的地址存放记录。需要注意的是，使用上面的哈希函数计算出来的地址范围是 0到 22，因此，从23到24这几个哈希地址实际上在一开始是不可能用哈希函数计算出来的，只可能在处理冲突时达到这些地址。 hash ( 962148 ) = 962148 % 23 = 12 三、处理冲突的方法 “处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址。 开放定址法 链地址法 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …, s 1. 开放定址法 对增量 di 有三种取法： 1) 线性探测再散列 di = c? i 最简单的情况 c=1 2) 平方(二次)探测再散列 di = 12, -12, 22, -22, …, 3) 随机探测再散列 di 是一组伪随机数列 或者 di=i×H2(key) (又称双散列函数探测) 例如: 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 19 01 23 14 55 68 19 01 23 14 68 若采用线性探测再散列处理冲突 若采用二次探测再散列处理冲突 11 82 36 55 11 82 36 1 1 2 1 3 6 2 5 1 1 1 2 1 2 1 4 1 3 将所有哈希地址相同的记录都链接在同一链表中。 2. 链地址法 0 1 2 3 4 5 6 14 01 36 19 82 23 11 68 55 ? ? ? ? ∧ ? ? ASL=(6×1+2×2+3)/9=13/9 同前例的关键字，哈希函数为 H(key)=key MOD 7 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为： 四、哈希表的查找 对于给定值 K， 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 否则 “求下一地址 Hi” ，直至 r[Hi] = NULL (查找不成功) 或 r[Hi].key = K (查找成功) 为止。 给定k值 计算H(k) 此地址为空 关键字==k 查找失败 查找成功 按处理冲突 方法计算Hi Y N Y N 哈希查找流程图 const int MaxSize = 11371; // 某个大于10000的素数 struct ElemType { // 元素结构 int key; // 关键字 char *info; // 其他信息 }; struct HashTable{ ElemType *elem; int count; // 当前数据元素个数，一般不用 }; enum Status{SUCCESS ,UNSUCCESS ,DUPLICATE}; //--- 开放定址哈希表的存储结构 --- Status SearchHash