伪随机探测再散列.PPT

* 2. 再哈希法 这种方法是同时构造多个不同的哈希函数：  Hi=RH1(key)， i=1，2， …， k 当哈希地址Hi=RH1(key)发生冲突时，再计算Hi=RH2(key),……,直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。 * 3. 链地址法 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。 链地址法适用于经常进行插入和删除的情况。  * 例如，已知一组关键字(32，40，36，53，16，46，71，27， 42，24，49，64)， 哈希表长度为13，哈希函数为：H(key)=key MOD 13，则用链地址法处理冲突的结果如右图所示。 64 24 36 49 46 32 71 16 42 40 27 53 0 1 2 3 4 5 6 7 8 9 10 11 12 * 4. 建立公共溢出区  这种方法的基本思想是将哈希表分为基本表和溢出表两部分，凡是与基本表发生冲突的记录一律填入溢出表。 * 9.3.4 哈希表的查找及其分析 哈希表的查找过程与哈希表的创建过程是一致的。当查找关键字为K的记录时: 首先计算p0=H(K)。 如果单元p0为空，则查找不成功；如果单元p0中记录的关键字为K，则查找成功；否则根据造表时设定的处理冲突的方法找出下一个哈希地址pi，直到哈希表中某个位置为“空”或者表中所填记录的关键字等于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(HashTable H, KeyType K, int p, int c) {// 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待//查数据元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并//返回UNSUCCESS, c用以记录冲突次数，其初值置零，供建表插入时参考 p = Hash(K); // 求得哈希地址 while (H.elem[p].key != NULLKEY // 该位置中填有记录 (H.elem[p].key != K)) // 并且关键字不相等 collision(p, ++c); // 求得下一探查地址p if (H.elem[p].key==K) return SUCCESS; // 查找成功，p返回待查数据元素位置 else return UNSUCCESS; // 查找不成功，p返回的是插入位置} // SearchHash * 我们可以通过调用查找算法实现开放定址哈希表的插入操作 Status InsertHash(HashTable H, Elemtype e) {// 查找不成功时插入数据元素e到开放定址哈希表H中，并返回// OK；若冲突次数过大，则重建哈希表 c = 0; if (SearchHash ( H, e.key, p, c ) == SUCCESS ) return DUPLICATE; // 表中已有与e有相同关键字的元素 else if (c hashsize[H.sizeindex]/2 ) { // 冲突次数c未达到上限， // (阀值c可调)