散列学习

//整数的散列

//m个数在n个数中是否出现过的散列 

#include<cstdio>
using namespace std;
int const Maxn = 100010;
bool hashTable[Maxn] = {false};
int main(){
	int n,m,x;//x表示出现的数,n表示对比的数的数量，m表示对比的数的数量 
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		hashTable[x] = true;
	}
	for(int i=0;i<m;i++){
		scanf("%d",&x);
		if(hashTable[x] == true){
			printf("%d出现过
",x);
		}else{
			printf("%d没出现过
",x);
		} 
	} 
	return 0;
} 

　　散列就是用空间换时间，为了降低时间复杂度，把输入的数用做数组的下标来进行数据性质的统计；

　　常用散列函数：直接地址法，平方取中法，除留余数法（最实用）；

　　为了避免除留余数法的冲突，通常我们还会有三种方法去避免冲突：线性探查法，平方探查法，链地址法；

　　做OJ时无需写该方法，可以用map来直接实用hash的功能。