教你几招HASH表查找的方法 (2)

优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素

缺点：能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率

二次探测法

di = 12, -12, 22, -22, …±k2

伪随机探测法

Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：m为哈希表长度
di 为随机数

开放定址法建立哈希表步骤

取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行step2解决冲突

根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找 到能用的存储地址为止

开放定址哈希表的存储结构

/* ------------- 开放定址哈希表的存储结构 ------------- */ 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 = Hash(K); // 求得哈希地址 while(H.elem[p].key != NULLKEY && !EQ(K, H.elem[p].key)) collisiion(p, ++c); // 求得下一探测地址p if(EQ(K, H.elem[p].key)) return SUCCESS; // 查找成功，返回待查数据元素位置 p else return UNSUCCESS; // 查找不成功 }