入门篇（2）-算法初步-散列

（1）散列定义与整数散列

散列（hash）是最常用的算法之一

#include<cstdio>
const int maxn =100010;
int hashTable[maxn]= {0}; //  数组初始化值为false
int main() {
	int n,m,x;
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++) {
		scanf("%d",&x);
		hashTable[x]++;  //数字x出现过
	}
	for(int i=0; i< m; i++) {
		scanf("%d",&x);
		printf("%d\n",hashTable[x]);

	}
	return 0;
}

特点：就是直接把输入的数作为数组的下标来对这个数的性质进行统计。

这是一个利用空间换时间的策略。

问题:如果数组下标太大如111111111，或者一个字符串I love you 就不能直接作为数组下标了。

散列：hash,“将元素通过一个函数转换成整数，使得该整数可以尽量唯一地代表这个元素”。把这个转化函数称之为散列函数H,

如果元素在转换前是key那么转换后就是一个整数H(key)。

（2）字符串hash初步：

字符串hash是指将一个字符串S映射为一个整数，使得整数可以尽可能唯一代表字符串S.

先假设字符串均由大写字母A_{Z构成，视为0}25,

按照而二十六进制转换成十进制。

int hashFunc(char S[], int len){
	int id =0;
	for(int i=0;i<len;i++){
		id=id*26+(S[i]-'A'); //  将而十六进制转换为十进制 
	}
	return id; 
}

如果字符串出现了小写字母，那么可以把A_{Z作为0-25，a}z看作26~51， 这样变成了52进制转换为10进制

int hashFunc(char S[], int len) {
	int id =0;
	for(int i=0; i<len; i++) {
		if(S[i]<='Z'&&S[i]>='A') {
			id=id*26+(S[i]-'A'); //  将而十六进制转换为十进制
		} else if(S[i]<='z'&&S[i]>='a') {
			id=id*52+(S[i]-'a')+26;

		}
	}
	return id;
}

//查询字符串在n个字符串中出现地次数
#include<cstdio>
#include<string.h>
#include<cstring>
using namespace std;
const int maxn =100;
char S[maxn][maxn],temp[maxn];
int hashTable[26*26*26+10];
int hashFunc(char S[],int len) { //字符数组 ,和字符数组地长度。
	int id =0;
	for(int i=0; i<len-1; i++) {
		id=id*26+(S[i]-'A');

	}
	return id;

}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++) {
		scanf("%s",S[i]);
		int id=hashFunc(S[i],strlen(S[i]));
		hashTable[id]++;  //该字符串出现地次数+1
	}
	for( int i=0; i<m; i++) {
		scanf("%s",temp);
		int id=hashFunc(temp,strlen(temp));
		printf("%d  -> %d \n",id,hashTable[id]);
	}
	return 0;
}