PTA散列表平方探测法解决冲突

核心问题

  当所有的位置都被填上了，且不能插入关键词，要进入死循环了怎么办?

题目

  本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key)=key%TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i2）解决冲突.

注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。

输入格式

  首先第一行给出两个正整数 MSize（≤104）和 N（≤MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。

输出格式

  在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 -。输出间以 1 个空格分隔，行首尾不得有多余空格。

输入样例

4 4

10 6 4 15

输出样例

0 1 4 -

AC代码

​

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <map>

using namespace std;

int is(int n) {

    if(n == 1)return 0;

    if(n == 2 || n == 3)return 1;

    if(n % 6 != 1 && n % 6 != 5)return 0;

    for(int i = 5;i * i <= n;i += 6)

        if(n % i == 0 || n % (i + 2) == 0)return 0;

    return 1;

}

int main() {

    int m,n;

    int s,p,v[10007] = {0};

    scanf("%d %d",&m,&n);

    while(!is(m))m ++;

//因为平方以后只需要到m，就能完全探测到整个散列表，具体去看数学推导

    for(int i = 0;i < n;i ++) {

        p = -1;//判断是否插入成功

        scanf("%d",&s);

        for(int j = 0;j < m;j ++) {

            if(!v[(s + j * j) % m]) {

                v[(s + j * j) % m] = 1;

                p = (s + j * j) % m;

                break;

            }

        }

        if(i)putchar(' ');

        if(p == -1)printf("-");

        else printf("%d",p);

    }

}

核心代码

//让从i到n，如果关键词能够查下去的则一定能，否则不能

for(int j = 0;j < m;j ++) {

            if(!v[(s + j * j) % m]) {

                v[(s + j * j) % m] = 1;

                p = (s + j * j) % m;

                break;

            }

        }

PTA散列表平方探测法解决冲突的相关教程结束。