（本文转载，自己做了少许修正，若有侵权请联系删除）
简单了解散列（hash）算法思想
设分别有两个集合，分别有M个和N个元素。问N个元素中每个数是否在是否在M中出现过。
一个很直观的想法就是：分别输入两组数据，然后用两个for循环来遍历查找。 时间复杂度为O(MN)，当N M足够大的时候，显然效率会非常低。
所以我们不妨用空间换取时间，当输入M集合中的数据x的时候，我们都用一个数组hashTable[10000]（初始设置为0，默认每个元素都没在这个集合中出现过）来设置hashTable[x] = 1来表明这个数x在M中存在。 这样我们在输入N集合中的数据，直接将输入的这个数作为hashTable数组的下标，就会直接得到我们想要的结果。这是的时间复杂度就降到了O(M+N)。*
//下面是实现的代码
int m,n,hashTable[10000] = {0};
cin >>m>>n; //m和n指的是集合M和集合N的元素个数
for (int i = 0,x;i<m ;i++ ){
cin>>x;
hashTable[x] = 1;
}
for (int i = 0,x;i<n ;i++ ){
cin>>x;
if(hashTable[x] == 1){
cout<<"YES";
}else{
cout<<"NO";
}
}
这里的精华思想就是：将输入的数据直接作为数组的下标来记录数据的状态。
但是这个策略依旧存在很多问题：上面的问题将输入的数据大小控制在了10^5 ，但是如果我们输入的数据为大约为10^9 这么大时，或者甚至是字符串如（“Hello World”)时，就不能直接将他们作为数组下标了。所以我们这时的目标就是将这些数据转化为一个可用的整数下标，而这种方法就叫做——散列
什么是散列
散列用一句话来说就是：将输入的数据用一个函数转化为一个整数，使其尽量唯一的代表该元素。 我们不妨称这个转换函数为H，如果一个元素之前是key，那么它转化后就成了H(key)，下面我们来分类讨论一下。
先是整数hash
当key为整数的时候，有哪些常见的散列函数呢？一般有直接定址法、除留取余法和平方取中法等。
直接定址法
恒等变换：H(key) = key OR 线性变换：H(key) = a*key + b; 像上边的问题，我们就采用key直接作为下标的方法，这也是最常见最使用的散列应用。
平方取中法
是指取key2 的中间若干位当作hash值，这个我们一般不怎么用，这里就不说了。
除留取余法
这也是个比较实用的方法。表达式为
H(key) = key%mod;//mod 是选定的整数
显然当mod为素数的时候，H(key)尽可能会覆盖到[0,mod)的所有值。因此为了方便，我们取TSize为素数，而且mod = TSize。
但是我们可能会注意到，不同的两个key值，他们的hash可能时相同的，我们把这种情况称作冲突。 下面我们再介绍一些冲突的解决方法。
线性探查法
我们得到一个哈希值H(key)后，发现这个下标已经被其他元素使用，那么我们就查看H(key+1)是否被占用，如果依然冲突，那么我们就接着+1+1的往后找，如果超出表长，就跳到首位继续循环，显然这种方法会造成扎堆的现象，而且效率也不高。
平方探查法
这个是对线性探查法的改进，为了避免扎堆现象，我们规定好一个查找的顺序： H(key + 1²) 、 H(key - 1²) 、H(key + 2²) 、H(key - 2²) … 如果检查过程中，key + k²超过了表长，我们就把key + k²对表长取模。
拉链法
和上面两种方法不同，拉链法不计算新的值，他将所有哈希值相同的key连接成一个单链表，可以设定一个数组Link，以取余法的hash为例，使用拉链法解决冲突的数组范围是Link[0]~Link[mod]，Link[h]来存放哈希值为h的key。
字符串hash(太妙了)
字符串哈希就是将字符串转化为一个整数，使得该整数尽可能地唯一的表示这个字符串。 为了方便讨论，我们不妨设字母都是由大写字母A-Z组成，并且对应0-25这26个数字，那么这26个字母就对应转化成了26进制数，依据转十进制的思路，我们可以肯定得到一个唯一的整数，由此便可实现字符串到整数的映射。
int hashFunc(char c[] ,int len){
int id = 0;
for (int i = 0;i<len ;i++ ){
id = id*26 + (c[i] - 'A');
}
return id;
}
显然如果字符串的长度比较长，转化出来的整数就会很大，所以我们要注意len的长度。
如果字母里边包含小写字母怎么办，我们可以把a-z设定为26-51，这样就成了52进制转十进制了。
int hashFunc(char c[] ,int len){
int id = 0;
for (int i = 0;i<len ;i++ ){
if(c[i]>='A'&&c[i]<='Z'){
id = id*52 + (c[i] - 'A');
}else if(c[i]>='a'&&c[i]<='z'){
id = id*52 + (c[i] - 'a') + 26;
}
}
return id;
}
如果出现了数字，一般有两种解决方法，
- 按照上述方法，增加进制到62；
- 如果末位确定是个数字，那么前面的字母转化成整数后直接拼接上这个数字，例如BCD4，BCD转化为731，拼接上后面的4就是7314。
int hashFunc(char c[] ,int len){
int id = 0;
for (int i = 0;i<len ;i++ ){
id = id * 26 + (c[i] - 'A');
}
id = id * 10 + (c[len - 1] - '0');
return id;
}