数据结构实验之查找五：平方之哈希表

亦凉 2022-12-28 08:22 136阅读 0赞

## 数据结构实验之查找五：平方之哈希表 ##

Description  
给定的一组无重复数据的正整数，根据给定的哈希函数建立其对应hash表，哈希函数是H(Key)=Key%P，P是哈希表表长，P是素数，处理冲突的方法采**用平方探测方法，增量di=±i^2,i=1,2,3,…,m-1**

Input  
输入包含多组测试数据，到 EOF 结束。

每组数据的第1行给出两个正整数N(N <= 500)和P(P >= 2N的最小素数)，N是要插入到哈希表的元素个数，P是哈希表表长；第2行给出N个无重复元素的正整数，数据之间用空格间隔。

Output  
按输入数据的顺序输出各数在哈希表中的存储位置 (hash表下标从0开始)，数据之间以空格间隔，以平方探测方法处理冲突。

Sample  
Input  
4 11  
10 6 4 15  
9 11  
47 7 29 11 9 84 54 20 30  
Output  
10 6 4 5  
3 7 8 0 9 6 10 2 1

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int a[550];
    int p,t,n;
    int Hash(int x)//构建Hash函数 
    {
        
    	x=x%p;//哈希函数是H(Key)=Key%P 
    	if(a[x]==0)//有空间 
    	{
        
    		a[x]=1;
    		return x;
    	}
    	else//空间被占用 
    	{
        
    		for(int i=1;;i++)
    		{
        
    			t=(x+i*i)%p;//向右探测 
    			if(a[t]==0)
    			{
        
    				a[t]=1;
    				return t;
    			}
    			t=(x-i*i)%p;//向左探测 
    			if(a[t]==0)
    			{
        
    				a[t]=1;
    				return t;
    			}
    		}
    	}
    }
    int main()
    {
        
    	while(~scanf("%d %d",&n,&p))
    	{
        
    		memset(a,0,sizeof(a));//将数组a的值清为0,0为未占用，1为占用 
    		for(int i=0;i<n;i++)
    		{
        
    			int x;
    			scanf("%d",&x);
    			printf("%d",Hash(x));
    			if(i!=n-1)
    			printf(" ");
    			else
    			printf("\n");
    		}
    	}
    }

[哈希算法原理和实现][Link 1]  
[哈希查找之平方探测][Link 2]

[Link 1]: https://blog.csdn.net/qq_46359697/article/details/108559658
[Link 2]: https://n0th1n9.blog.csdn.net/article/details/78694496