第九章 查找研究.ppt

* 注意：增量 di 应具有“完备性” 即：产生的 Hi 均不相同，且所产生的 s(m-1)个 Hi 值能覆盖哈希表中所有 地址。则要求： ※ 平方探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, … 等）； ※ 随机探测时的 m 和 di 没有公因子。 * 例 表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中 0 1 2 3 4 5 6 7 8 9 10 60 17 29 (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 不冲突 38 (2) H(38)=38 MOD 11=5 冲突 H1=(5+12) MOD 11=6 冲突 H2=(5-12) MOD 11=4 不冲突 38 (3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突 38 * 例如: 给定关键字集合构造哈希表 { 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 * 将所有哈希地址相同的记录都链接在同一链表中。 例:给定关键字{ 19, 01, 23, 14, 55, 68, 11, 82,36 } 哈希函数为 H(key)=key MOD 7 链地址法 0 1 2 3 4 5 6 ? 11 ? 19 82 68 ? 55 ? 14 36 ? 01 ? 23 ? * 例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ * 再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址， 直到冲突不再发生。 即：Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的哈希函数 特点：计算时间增加 * 建立公共溢出区 设哈希函数的值域为[0,m-1]，则设向量HashTable[0..m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。 * 哈希查找过程 给定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 (查找成功) 为止。 * int hashsize[] = { 997, ... }; typedef struct { ElemType *elem; int count; // 当前数据元素个数 int sizeindex; // hashsize[sizeindex]为当前容量 } HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 开放定址哈希表的存储结构 * Status SearchHash (Ha