数据结构与算法-7-42 整型关键字的散列映射

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

输入格式:

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

输出格式:

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

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

这是一道hash基础题目。要注意，哈希表中已经有的数据，不要重复插入，直接输出下标即可。

代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int N, P;
  cin >> N >> P;
  vector<int> H(P, -1);
  for(int i = 0; i < N; i++){
    int num;
    cin >> num;
    int hash = num % P;
    while(1){
      if(hash >= P) hash -= P;
      if(H[hash] == num){
        cout << hash;
        break;
      }
      if(H[hash] == -1){
        H[hash] = num;
        cout << hash;
        break;
      }else hash++;
    }
    if(i!=N-1) cout << ' ';
  }
  return 0;
}