DS哈希查找—二次探测再散列
大家好，又见面了，我是你们的朋友全栈君。
题目描述
定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。
输入
测试次数t
每组测试数据格式如下：
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字
输出
对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL
对k个待查关键字，分别输出：
0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
样例输入
1
12 10
22 19 21 8 9 30 33 4 41 13
4
22
15
30
41
样例输出
22 9 13 NULL 4 41 NULL 30 19 8 21 33
1 1 1
0 3
1 3 8
1 6 6
思路：
取key的方式：先取余，若不冲突则直接存，若冲突则加上偏移量(1²,-1²,2²,-2²……)，然后在长为m的hash表中循环滚动，最后确定key
key第一次取value%11
如果位置冲突，key取：value % 11 + 1²，如果key超过hash表的长度m，key取key-m，如果key的值为负，key取key+m
如果位置冲突，key取：value % 11 + （-1²），如果key超过hash表的长度m，key取key-m，如果key的值为负，key取key+m
如果位置冲突，key取：value % 11 + （2²），如果key超过hash表的长度m，key取key-m，如果key的值为负，key取key+m
如果位置冲突，key取：value % 11 + （-2²），如果key超过hash表的长度m，key取key-m，如果key的值为负，key取key+m
以此类推下去取key
code:
#include <iostream>
using namespace std;
void test()
{
int m,n;
cin>>m>>n;
int *hashh;
hashh = new int [m];
for(int i=0;i<m;i++)
hashh[i]=-100000;
int value,key,flag,temp_key,d,symb,num;
for(int i=0;i<n;i++) //建hash表
{
cin>>value;
key=value%11;
temp_key=key;
d=1; //偏移量
symb=1; //符号
num=0; //hash次数
while(1)
{
if(hashh[temp_key]==-100000)
{
hashh[temp_key]=value;
break;
}
else
{ //滚动取key
num++;
temp_key=key+symb*(d*d); //更新key
symb*=-1; //更新符号
if(num%2==0) //每2次需要更新1次偏移量
d++;
if(temp_key>m) //key超过hash表长度
temp_key -= m;
else if(temp_key <0) //key的值为负数
temp_key += m;
}
}
}
for(int i=0;i<m;i++)
{
if(hashh[i] == -100000)
cout<<"NULL";
else
cout<<hashh[i];
if(i != m-1)
cout<<' ';
}
cout<<endl;
int search_num,search_time;
cin>>search_num;
for(int i=0;i<search_num;i++) //查找
{
search_time=0;
cin>>value;
key=value%11;
temp_key=key;
d=1;
symb=1;
flag=0;
num=0;
while(1)
{
search_time++;
if(hashh[temp_key]==value)
{
flag=1;
cout<<1<<' '<<search_time<<' '<<temp_key+1<<endl;
break;
}
else
{ //和建表一样的更新方法
if(hashh[temp_key]==-100000)
break;
num++;
temp_key=key+symb*(d*d);
symb*=-1;
if(num%2==0)
d++;
if(temp_key>m)
temp_key -= m;
else if(temp_key <0)
temp_key += m;
if(num>m/2)
break;
}
}
if(flag==0)
cout<<0<<' '<<search_time<<endl;
}
delete[] hashh;
}
int main()
{
int t;
cin >> t;
while (t--)
{
test();
}
return 0;
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/146468.html原文链接：https://javaforall.cn