算法 散列hash的含义以及使用方法

散列要解决的问题

有m个数，要分别知道他们的每一个是否在n个数中出现过，以及出现了多少次，可以用一个整型的散列表来解决这个问题。

1. 原始思路：对m个数分别读入，然后在n个数中逐一比对，暴力求解，算法复杂度o(MN)
2. 初级思路：读入n个数，以数值大小直接作为下标，建立一个hash表，算法复杂度o(M+N)
3. 进阶思路：读入n个元素(不仅局限在数，还可以是字符串等)，把他们通过函数转为一个整数，使这个整数尽量唯一代表这个元素，然后用这个整数作为下标，建立hash表

典型应用

给出n个字符串，由三位大写字母组成，再给出m个查询字符串，问每个查询字符串在n个字符串中出现的次数。

#include<cstdio>
using namespace std;
const int maxn = 26 * 26 * 26 + 10;
int hash[maxn] = {0};

int hashFunc(char s[],int len){   //hash函数，将三位字符串转为hash值
	int id = 0;
	for(int i = 0 ; i < len; i++){
		id = id * 26 + (s[i] - 'A');
	}
	return id;
} 

int main()
{
	int n,m;
	char temp[3];
	scanf("%d%d",&n,&m);
	for(int i = 0; i < n; i++){
		scanf("%s",temp);
		hash[hashFunc(temp,3)]++;
	}
	for(int i = 0; i < m; i++){
		scanf("%s",temp);
		printf("%d\n",hash[hashFunc(temp,3)]);
	}
	return 0;
}