4 整型关键字的散列映射

4 整型关键字的散列映射

分数 25
作者 DS课程组
单位 浙江大学

给定一系列整型关键字和素数P，用除留余数法定义的散列函数H(Key)=Key将关键字映射到长度为P的散列表中。用线性探测法解决冲突。

输入格式:

输入第一行首先给出两个正整数N（≤1000）和P（≥N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个整型关键字。数字间以空格分隔。

输出格式:

在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C++ (g++)

思路：

这个就是我们将每个数对P取余的结果分别对应在散列表中的位置，如果位置已经被占了的话，那么就用线性探测法解决冲突。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,P,x,y;
    cin>>N>>P;
    int a[P]={0};
    for(int i=0;i<N;i++){
        int k=1;
        cin>>x;
        y=x%P;
        while(a[y]!=0&&a[y]!=x){
            y=(x+k)%P;
            k++;
        }
        a[y]=x;
        if(i!=0) cout<<" ";
        cout<<y;
    }
    return 0;
}