散列的基本介绍

散列的算法思想十分经典，让我们用一个十分巧妙的空间换时间策略来作为该篇文章的开头：
给你N个正整数，再给你M个正整数，问这M个数是否分别在N个数中出现过？

关于这道题的解法，最直观的策略就是开一个嵌套循环，然后遍历。但这样做的时间复杂度为O(M*N)，在M和N非常大的情况下，这个策略的时间复杂度非常糟糕。

于是我们就想到了用空间换时间的策略，即开一个M（假设这里M、N均小于10⁵)长度的数组bool hashtable[100010],hashtable[x]=true代表x在N个正整数中出现过，而false代表没出现过。这样就可以逐个输入M个数并将其对应下标的hashtable数组里的元素变为true，然后再用N直接查找对应位置的hashtable，如果为true，代表M里有这个数，否则就没有。这样做的时间复杂度为O(M+N)，为O(1)级别，和O(M*N)相比，时间复杂度显然得到了巨大的优化。

同理，如果求M个欲查询的数中每个数在N个数中出现的次数，也可以用上述思想。

上述两个问题解法都有一个共同的思想：直接把输入的数作为数组的下标来对这个数的性质进行统计。

而上述解法仍有其局限性，如果我想要转化的数很大，或者我想把字符串转化成整数怎么办？这时候我们的主角就要登场了，那就是散列（hash）。
散列可以一言以蔽之：将元素通过函数关系转换成一个整数，使这个整数能唯一地表示这个元素。

如果把转换前的元素称为key，用于转换的散列函数为H，那个转换后的整数就是H（key)。

下面介绍一些常用的散列函数：

1.直接定址法：H（key)=key，上述两个例题用的就是直接定址法。
2.线性变换：H（key)=a*key+b
3.除留余数法。这是比较常用的一种方法。除留余数法指的是把key除以一个数mod得到的余数作为hash值得方法。
第三个方法会产生“冲突”，即两个key值可能有相同得key，这时我们会用三种办法来解决：
1.线性探查法
2.平方探查法
3.链地址法
这三个方法不做深入讨论。

最后，介绍一下字符串hash：

先讨论将全部是大写字母的字符串S转化成整数：
设A~Z分别对应0至25，这时便可以把该字符串当作二十六进制数，再用进制转换变为十进制数，即完成了字符串hash。代码如下：

int hashfunc(char s[],int len)
{
     int id=0;
     for(int i=0;i<len;i++)
     {
         id=id*26+(s[i]-'A');
     }
     return id;
}

再来看有大小写字母的字符串，这里可直接看成是五十二进制数，思路和大写字母的字符串一样。代码如下：

int hashfunc(char s[],int len)
{
    int id=0;
    for(int i=0;i<len;i++)
    {
        if(s[i]>='A'&&s[i]<='Z')
            id=id*52+(s[i]-'A');
        if(s[i]>='a'&&s[i]<='z')
            id=id*52+(s[i]-'a');
    }
    return id;
}

如果出现了数字，一般有两种方法：
1.将进制变为62。
2.若数字仅出现在字符串尾部，且位数确定，则可以直接算出前面字母对应的整数，然后再直接加上后面的数字。如BCD4，将BCD转变为731，再拼接上4变为7314即可。

最后以一个题目结尾：

输入N个字符串，每个字符串恰好由三个大写字母组成，再输入M个查询字符串，问每个查询字符串在N个字符串中出现的次数。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
char s[maxn][5];
int hashtable[26*26*26+10];//防止溢出,注意全局变量中的数组默认值为0
int hashfunc(char s[],int len)//哈希函数，将字符串转化为整数
{
    int id=0;
    for(int i=0;i<len;i++)
    {
        id=id*26+(s[i]-'A');
    }
    return id;
}
int main()
{
    int n,m,id;
    char temp[5];
    scanf("%d%d",&n,&m);
    int i;
    for(i=0;i<n;i++)//更新哈希表
    {
        scanf("%s",s[i]);
        id=hashfunc(s[i],3);
        hashtable[id]++;
    }
    for(i=0;i<m;i++)//按哈希表中的数值输出统计结果
    {
        scanf("%s",temp);
        id=hashfunc(temp,3);
        cout<<hashtable[id]<<endl;
    }
    return 0;
}