哈希表的查找和算法
数据结构的一道题目：设有一组关键字{12,11,35,25,22,58}，采用哈希函数:H(key)=key%6，采用开放
地址法的二次探测再哈希方法解决冲突，试在0~10的哈希地址空间中对该关键字序列
构造哈希表。
解法：
依题，m=11，二次探测再哈希的下一地址计算公式为
d1=H(key),
d2=(d1+i*i)%m,
d3=(d1-i*i)%m
其中(i=1,2,3,...)
则有：
H(12)=12%6=0
H(11)=11%6=5
H(35)=35%6=5(冲突)
H(35)=(5+1*1)%11=6
H(25)=25%6=1
H(22)=22%6=4
H(58)=58%6=4(冲突)
H(58)=(4+1*1)%11=5(冲突)
H(58)=(4-1*1)%11=3
对应的构造算法实现：
#include<iostream>using namespace std;void CrtHash(int a[],int val,int n1,int n2){int temp=val%n1; //没有冲突if(a==0){a=val;return;}else //发生冲突{int temp1;for(int j=1;;++j){temp1=(temp+j*j)%n2;if(a==0){a=val;return;}temp1=(temp-j*j)%n2;if(a==0){a=val;return;}}}}int main(){int KEY={12,11,35,25,22,58};int hashtable;memset(hashtable,0,sizeof(hashtable));for(int i=0;i<6;++i){ CrtHash(hashtable,KEY,6,11);}for(int i=0;i<11;++i){ cout<<hashtable<<" ";}return 0;}
页:
[1]