Hashing (25)

#include <iostream>
using namespace std;
bool isprime(int n){                  //判断是否为素数
    if(n<=1) return false;
    if(n==2) return true;
    for(int i=2;i<n;i++){
        if(n%i==0) return false;
    }
    return true;
}
int main(){
    int n,tsize,temp,s[10010]={0};
    cin>>tsize>>n;
    while(!isprime(tsize))          //找到最近的素数作为哈希表长度
        tsize++;
    for(int i=0;i<n;i++){
        cin>>temp;
        int j,k;
        for(j=0;j<tsize;j++){
            k=(temp+j*j)%tsize;    //平方探测法
            if(!s[k]){
                s[k]=1;
                cout<<k;
                break;
            }
        }
        if(j==tsize) cout<<"-";   //没有找到插入位置
        if(i!=n-1) cout<<" ";
    }
    return 0;
}

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();//table size
		int n = in.nextInt();//input size
		int[] input = new int[n];
		for(int i = 0;i<n;i++)
			input[i] = in.nextInt();
		m = re(m);
		int[] table = new int[m];
		for(int i = 0;i<n;i++){
			int key = input[i];
			int index = key%m;
			int inc = 1;
			while(inc<m&&table[index]!=0){
				index = (key+inc*inc)%m;
				inc++;
			}
			if(table[index]==0){
				table[index] = key;
				System.out.print(index);
			}else{
				System.out.print("-");
			}
			if(i+1!=n)
				System.out.print(" ");
		}
		System.out.println();
	}
	private static int re(int size){
		if(size<=2)
			return 2;
		while(!isPrime(size))
			size++;
		return size;
	}
	private static boolean isPrime(int num){
		int limit = (int)Math.sqrt(num);
		for(int i = 2;i<=limit;i++)
			if(num%i==0)
				return false;
		return true;
	}
}

#include <iostream>
#include <cmath> 

using namespace std;

bool isPrime(int n)
{     if(n==1)         return false;     if(n==2)         return true;     for(int i=2;i<=sqrt(n);i++)         if(n%i==0)             return false;     return true;
}

int main()
{     int n,tsize,x;     bool v[10007]={false};     cin>>tsize>>n;     while(!isPrime(tsize))         tsize++;     for(int i=0;i<n;i++)     {         cin>>x;         int d,k;         for(d=0;d<tsize;d++)         {             k = (x+d*d)%tsize;             if(!v[k])             {                 v[k] = true;                 cout<<k;                 break;             }         }         if(d==tsize)             cout<<"-";         if(i!=n-1)             cout<<" ";     }     return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int Max=1e5;
bool hashtable[Max];

bool isprime(int n){
	if(n<2) return 0;
	int l=sqrt(n*1.0);
	for(int i=2;i<=l;i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

int main(){
    ios::sync_with_stdio(0);
	int n,m;
	cin>>n>>m;
	while(!isprime(n)){
		n++;
	}
	int k,a;
	for(int i=0;i<m;i++){
		cin>>k;
		a=k%n;
		if(!hashtable[a]){
			hashtable[a]=1;
			if(i==0) cout<<a;
			else{
				cout<<" "<<a;
			}
		}else{
			int step;
			for(step=1;step<m;step++){
				a=(k+step*step)%n;
				if(!hashtable[a]){
					hashtable[a]=1;
					cout<<" "<<a;
					break;
				}
			}
			if(step==m){
				cout<<" "<<'-';
			}
		}
	}
	return 0;
}

更多PAT甲级题解--acking-you.github.io

题目

OJ平台

题目大意

题目中两句话最为核心：

1. Quadratic probing (with positive increments only) is used to solve the collisions.
   二次探测(只有正增量)被用来解决冲突。
   讲人话就是：用只有正增量的二次探测方法来解决哈希冲突。
   2. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
      如果给定的最大长度不是一个质数，你必须重新定义这个表长，重新定义的表长长度是大于原长度的最小质数。

怎么用二次探测法解决哈希冲突?

二次探测，实际上非常简单，就是通过枚举 -i^2 或者 +i^2 来进行试探，是否该位置出现哈希冲突，直到没有出现哈希冲突为止，这样的话，只要哈希表不满，就不可能出现哈希冲突了。

• 而这题的要求是只有正增量，这说明只通过 +i^2 来实现二次探测。

以下为此题的二次探测

//@核心机制！--平方探测法防止哈希冲突
int detect(int num) { //这个二次探测法搞了好久--终于过了！！！
//注意一定要j<MaxS不能j*j<=MaxS,就因为写个j*j<MaxS导致浪费了三个小时！！！
    int k;
    for (int j = 0; j < MaxS; j++) {
        k = (num + j * j) % MaxS; //平方探测法
        if (!visit[k])break;
    }
    return k;
}

解题代码详解

基本变量

int MaxS, N;
int* res = nullptr; //用动态方式申请内存，存储答案
bitset<MaxN>IsPrim; //质数筛
bitset<MaxN>visit; //用于防止hash冲突的记录表

预处理函数

• 这题的预处理，我使用质数筛来进行质数的判断，所以先更新质数筛，以及还有一个找质数的函数。

  //@更新质数筛
  void update() {
    IsPrim.set();//所有位设置为1
    IsPrim[0] = IsPrim[1] = 0;
    for (int i = 2; i <= (int)sqrt(MaxN); i++) {
        if (IsPrim[i]) {
            int j = i, k = i;
            while (j * k <= MaxN) {
                IsPrim[j * k] = 0;
                k++;
            }
        }
    }
  }
  //@找到最近的素数
  void re_define() { //找出最接近的质数进行重新赋值
    int x = MaxS;
    while (!IsPrim[x])   x++;
    MaxS = x;
  }

  输入处理

  //@输入处理
  void Input() {
    ios::sync_with_stdio(false);
    cin >> MaxS >> N;
    res = new int[N];
    re_define();
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        int key = detect(num);
        if (visit[key]) {
            res[i] = -1; //其实可以边输入边打印的，但我这边为了使代码逻辑清晰用res数组存下
        } else {
            res[i] = key;
            visit[key] = 1;
        }
    }
  }

  输出处理

  //@打印答案
  void print() {
    for (int i = 0; i < N; i++) {
        if (res[i] != -1) {
            cout << res[i];
        } else {
            cout << '-';
        }
        if (i != N - 1)
            cout << ' ';
    }
  }

整合代码得出答案

#include<bits/stdc++.h>
#define MaxN 10001
using namespace std;
int MaxS, N;
int* res = nullptr;
bitset<MaxN>IsPrim; //质数筛
bitset<MaxN>visit; //用于防止hash冲突的记录表

//@预处理过程
//更新质数筛
void update() {
    IsPrim.set();//所有位设置为1
    IsPrim[0] = IsPrim[1] = 0;
    for (int i = 2; i <= (int)sqrt(MaxN); i++) {
        if (IsPrim[i]) {
            int j = i, k = i;
            while (j * k <= MaxN) {
                IsPrim[j * k] = 0;
                k++;
            }
        }
    }
}
//找到最近的素数
void re_define() { //找出最接近的质数进行重新赋值
    int x = MaxS;
    while (!IsPrim[x])   x++;
    MaxS = x;
}


//@核心机制！--平方探测法防止哈希冲突
int detect(int num) { //这个二次探测法搞了好久--终于过了！！！
//注意一定要j<MaxS不能j*j<=MaxS,就因为写个j*j<MaxS导致浪费了三个小时！！！
    int k;
    for (int j = 0; j < MaxS; j++) {
        k = (num + j * j) % MaxS; //平方探测法
        if (!visit[k])break;
    }
    return k;
}

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> MaxS >> N;
    res = new int[N];
    re_define();
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        int key = detect(num);
        if (visit[key]) {
            res[i] = -1; //其实可以边输入边打印的，但我这边为了使代码逻辑清晰用res数组存下
        } else {
            res[i] = key;
            visit[key] = 1;
        }
    }
}
//@输出处理
void print() {
    for (int i = 0; i < N; i++) {
        if (res[i] != -1) {
            cout << res[i];
        } else {
            cout << '-';
        }
        if (i != N - 1)
            cout << ' ';
    }
}

int main() {
    update();
    Input();
    print();
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
(842)#include <iostream>
#include <algorithm>
(831)#include <cmath>
#include <string>
(765)#include <set>
#include <vector>
(721)#include <map>
#include <iomanip>
(843)#include <sstream>
using namespace std;

//1078 Hashing
//对输入的m，若不是素数则要返回大于它的最近素数。
//



//埃氏
const int maxn = 10010;
vector<bool> is_pri(maxn, true); //初始化为true


int get_prime(int x) {
	for (int i = x + 1; i < maxn; ++i) {
		if (is_pri[i]) return i;
	}
}


int m, n;
int used[maxn] = {};

int get_idx(int num) {
	int idx = num % m;
	if (!used[idx]) {
		used[idx] = 1;
		return idx;
	}
	else {
		//平方探测法
		int new_idx;
		for (int j = 1; j <= m / 2; ++j) { //遍历过m/2就算完成
			new_idx = (idx + j * j) % m;
			if (!used[new_idx]) {
				used[new_idx] = 1;
				return new_idx;
			}
		}
		//到此说明没找到合适位置
		return -1;
	}
}

int main() {

	//筛数
	is_pri[0] = is_pri[1] = false;
	for (int i = 2; i < maxn; i++) {
		if (is_pri[i]) {
			//若i为素数，则去掉i的倍数
			for (int j = 2 * i; j < maxn; j += i) {
				is_pri[j] = false;
			}
		}
	}

	//读数据
	cin >> m >> n;
	//更新m为素数
	if (!is_pri[m]) {
		m = get_prime(m);
	}

	//插入
	int num, pos;
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d", &num);
		pos = get_idx(num);
		if (pos == -1) cout << '-';
		else cout << pos;
		cout << " ";
	}

	//末位不留空
	scanf("%d", &num);
	pos = get_idx(num);
	if (pos == -1) cout << '-';
	else cout << pos;


	return 0;
}

PAT那边题目说的数据都是正数，但是测试用例不完全是，坑

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 10005;
int table[MAXN];
int num[MAXN];
int n,m;

bool isPrime(int m)
{
    if(m==1)    return false;
    if(m==2)    return true;
    for(int i=2;i<=(int)sqrt(m);i++)
    {
        if(m%i==0)
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    while(!isPrime(m))
        m++;
    for(int i=0;i<n;i++)
    {
        int pos_t = num[i]%m;
        int j;
        for(j=0;j<m;j++)
        {
            if(table[(pos_t+j*j)%m]==0)
            {
                pos_t = (pos_t+j*j)%m;
                table[pos_t] = 1;
                break;
            }
        }
        if(i)
            cout<<' ';
        if(j==m)
            cout<<'-';
        else
            cout<<pos_t;
    }
}

Msize,N=map(int,input().split())
inList=list(map(int,input().split()))
def prime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
while Msize<2 or not prime(Msize):
    Msize+=1
Hash,res=[None]*Msize,[None]*N
for i in range(N):
    for j in range(Msize):
        t=(inList[i]+j*j)%Msize
        if not Hash[t]:
            Hash[t],res[i]=inList[i],str(t)
            break
    else:
        res[i]='-'
print(' '.join(res))

采用平方探测，说实话忘了。参考最高赞同
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
using namespace std;
#define Debug
#ifdef Debug
ifstream ifile("case.txt");
#define cin ifile
#endif


int Prime(int x)
{
    if (x == 1)
        return 3;

    for (int i = x; ; i++)
    {
        if (i % 2 == 0)
            continue;
        bool check = true;
        for (int j = 2; j <= sqrt(i); j++)
        {
            if (i % j == 0)
            {
                check = false;
                break;
            }
        }
        if (check)
        {
            x = i;
            break;
        }
    }
    return x;
}

int main()
{
    //H(key) = key % TSize
    int mSize, n;//table size number
    cin >> mSize >> n;
    mSize = Prime(mSize);
    vector<int> v(mSize);
    int tmp;

    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        if (v[tmp % mSize] == 0)
        {
            v[tmp % mSize] = 1;
            if (i == 0)
                cout << tmp % mSize;
            else
            {
                cout << " " << tmp % mSize;
            }
        }
        else
        {
            bool check = false;
            for (int i = 1; i < mSize; i++)
            {
                if (v[(tmp + i * i) % mSize] == 0)
                {
                    v[(tmp + i * i) % mSize] = 1;
                    check = true;
                    cout << " " << (tmp + i * i) % mSize;
                    break;
                }
            }
            if(!check)
                cout << " -";
        }
    }
    system("pause");
}

//wa了10发左右，坑点是二次探测(Quadratic probing)，
//如果用二次探测都没有找到可以insert的位置,就输出'-'.
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6;
vector<int> primes;
int vis[maxn],MSize,N;
set<int> st;
void init(){
    int m=sqrt(1e5);
    for(int i=2;i<=m;++i)
        if(!vis[i]){
            for(int j=i*i;j<=1e5;j+=i)
                vis[j]=1;
        }
    for(int i=2;i<=1e5-100;++i)
        if(!vis[i])
            primes.push_back(i);        
}
int main(){
    init(); 
    scanf("%d %d",&MSize,&N);
    auto it=lower_bound(primes.begin(),primes.end(),MSize);
    MSize=*it;
//cout<<MSize<<endl;
    for(int i=1,tmp;i<=N;++i){
        scanf("%d",&tmp);int ok=0,ans;
        for(int k=0;k<=MSize;++k){
            if(!st.count((tmp+k*k)%MSize)){
                ans=(tmp+k*k)%MSize;st.insert(ans);ok=1;break; 
            }
        }
        if(i==1){
            printf("%d",ans);
        }else{
            if(ok) printf(" %d",ans);
            else printf(" -");
        }
    }    
    return 0;
}

#include<iostream>
#include<math.h>
using namespace std;
bool isPrime(int n) {
    if (n == 2) return true;
    if (n == 1) return false;
    int bound = sqrt(n) + 1;
    for (int i = 2; i <= bound; i++) {
        if (n%i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int size, n;
    cin >> size >> n;
    if (isPrime(size)) {}
    else {
        while (!isPrime(++size));
    }
    int *table = new int[size];
    for (int i = 0; i < size; i++) {
        table[i] = -1;
    }
    int temp;
    
    for (int i = 0; i < n; i++) {
        cin >> temp;
        int det = 0;
        int pos = 0;
        bool flag = false;
        while (det <= size) {
            pos = (temp%size + det*det) % size;
            if (table[pos] == -1) {
                table[pos] = temp;
                flag = true;
                break;
            }
            det++;
        }
        if (flag) {
            cout << pos;
        }
        else {
            cout << "-";
        }
        if (i != n - 1) {
            cout << " ";
        }
    }
}

计算实际size，对每个尝试插入即可。二次探查只要计算到(num + size * size)之前就够了，后面取余的结果都是重复的。

#include <cstdio>
#include <cstdlib>

int Msize, n; 
int size;
int hash[10000];

bool isPrime(int num){
    if(num < 2) return false;
    for(int i = 2; i * i <= num; i ++){
        if(num % i == 0){
            return false;
        }
    }
    return true;
}

int insert(int num){
    int pos = num % size, finalPos = -1;
    if(hash[pos] == 0){
        finalPos = pos;
    }else{
        for(int i = 1; i < size; i ++){
            if(hash[(num + i * i) % size] == 0){
                finalPos = (num + i * i) % size;
            }
        }
    }
    if(finalPos >= 0){
        hash[finalPos] = num;
    }
    return finalPos;
}

int main(){
    scanf("%d %d", &Msize, &n);
    for(size = Msize; size < (1 << 30); size ++){
        if(isPrime(size)) break;
    }

    int ans, num;
    char c = ' ';
    for(int i = 0; i < n; i ++){
        scanf("%d", &num);
        ans = insert(num);
        if(i == n - 1) c = '\n';
        if(ans != -1){
            printf("%d%c", ans, c);            
        }else{
            printf("-%c", c);
        }
    }

    return 0;
}

#include <iostream>
using namespace std;
bool marked[10010];						//注意9973的下一个素数是10007
//判断是否是素数的函数
bool is_prime(int x) {
	if (x < 2)		return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}

int main(void) {
    int msize, n, num, i;
    
    cin >> msize >> n;
    for (i = msize; ; i++) {
        if (is_prime(i)) {
            msize = i;
            break;
        }
    }   
    for (i = 0; i < n; i++) {
        cin >> num;
        int h = num % msize;				//初始散列位置
		int hash = h;
		bool flag = false;					//是否散列成功
        for (int k = 0; k < msize; k++) {    
			hash = (h + k * k) % msize;		//二次探测法
            if (!marked[hash]) {			//成功找到位置
                marked[hash] = true;
				flag = true;
                break;
            }
        }        
		if (flag)		cout << hash;
		else			cout << "-";
        if (i != n-1)   cout << " ";
        else            cout << endl;
    }
    
    return 0;
}

#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=10001;
int prime[maxn],num=0;
bool is[maxn]={false};
bool isprime(int n)
{
	if(n<=1)
		return false;
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++)//////////////
		if(n%i==0)
			return false;
	return true;
}

int main()
{
	int m,tbsize;
	int x;
	scanf("%d%d",&tbsize,&m);
	while(isprime(tbsize)==false)
		tbsize++;

	for(int i=0;i<m;i++)
	{
		scanf("%d",&x);
		int n=x%tbsize;
		if(is[n]==false)
		{
			is[n]=true;
			if(i==0)
				printf("%d",n);
			else
				printf(" %d",n);
		}else{
			int p;
			for(p=1;p<tbsize;p++)
			{
				n=(x+p*p)%tbsize;
				if(is[n]==false)
				{
					is[n]=true;
					if(i==0)
						printf("%d",n);
					else
						printf(" %d",n);
					break;
				}
			}
			if(p>=tbsize)
			{
				if(i>0)
					printf(" ");
				printf("-");
			}
		}
	}
	return 0;
}