Hashing - Average Search Time

PAT-1145

需要注意本题的table的容量设置
二次探测，只考虑正增量
这里计算平均查找长度的方法和书本中的不同

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<sstream>

#include<set>

#include<map>

#include<cmath>

using namespace std;

const int maxn=10004;

int table[100*maxn];

int size,n,m;

bool isPrime(int n){

	if(n<=1){

		return false;

	}

	for(int i=2;i*i<=n;i++){

		if(n%i==0)

			return false;

	}

	return true;

}

int findPrime(int n){

	while(!isPrime(n)){

		n++;

	}

	return n;

}

bool insertHash(int n){

	int ori=n;

	bool flag=false;

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

		if(table[(n+j*j)%size]==-1){

			table[(n+j*j)%size]=ori;

			flag=true;

			break;

		}

	}

	return flag;

}

int findHash(int n){

	//返回次数

	int ans=0;

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

		ans++;

		if(table[(n+j*j)%size]==-1||table[(n+j*j)%size]==n)

			break;

	}

	return ans;

}

int main(){

	memset(table,-1,sizeof(table));

	cin>>size>>n>>m;

	size=findPrime(size);

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

		int a;

		cin>>a;

		if(!insertHash(a)){

			cout<<a<<" cannot be inserted."<<endl;

		}

	}

	int sums=0;

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

		int b;

		cin>>b;

		sums+=findHash(b);

	}

	printf("%.1lf\n",sums*1.0/m);

	return 0;

}

巴特西

PAT-1145（Hashing - Average Search Time）哈希表+二次探测解决冲突

Hashing - Average Search Time

PAT-1145

最新文章

热门文章