散列的使用

一.散列定义与整数散列

概括：将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素。

作用：用空间换取时间，使时间复杂度能够减少，如第一个例子，由直接对比的O（N*M）简化为O（N+M）

整数散列函数分类：对于key是整数的情况，常用的有直接定址法、除留余数法、平方取中法（较少用）。

1.直接定址法

解释：指的是恒等变换（H（key）=key）或线性变换（H（key）=key*a+b）。

局限：如果数值很大，则给出的数组空间太大，而且容易浪费。

例子：给出N个整数和M个整数，如{8,3,7,6,2}和{7,4,2}，N,M<=10^5，问在N中是否出现有M以及M在N中的出现次数，且有则输出yes和次数，否则输出no。

解决思路：将N个整数视为地址（下标），M个整数视为M个key，可以创建10001个空间的数组，把N个整数代表的下标在数组做标记（判true，或+1），然后遍历M个整数，查看对应下标的数组值是否大于0。

#include <iostream>
using namespace std;
int hashTable[100001] = { 0 };

int main() {
    int n, m, x;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        hashTable[x]++;        //记录M在N中出现次数
    }
    for (int i = 0; i < m; i++)
    {
        cin >> x;
        cout <<hashTable[x]<<endl;  //输出次数
    }
    return 0;
}

 2.除留余数法

解释：H（key）=key%mod。冲突是不可避免的。

注意：表长必须＞=mod值，不然会越界。而且mod值取素数，能尽可能覆盖【0，mod)的每个数，为方便，取表长=mod值=一个素数。

冲突解决方法：线性探查法，平方探查法，链地址法。

 二.字符串hash初步

当key不是整数，而是字符串时（如大写字母，小写字母和数字），或者说是二维坐标（x,y），并且0<<key<<range那该怎么让key能够唯一地由整数代表。

思路：对于二维坐标P，令hash函数为H（P）=x*range+y，即可得到唯一的整数，任意的二维坐标都不会有相同的整数，接着就能用整数hash的方法进一步映射到较小的范围。

同理，对于字符串S，如大写字母A到Z有26个，视为整数0到25，range就是26，也就对应二十六进制，然后再把二十六进制转换为十进制，这个十进制数一定是唯一的，就可实现将字符串映射为唯一整数的需求，如有长度为3的字符串，则整数范围就是26^3-1。

int hashFunc(char S[],int len){
   int id = 0;
   for(int i=0;i<len;i++)
      id = id*26 + (S[i] - 'A');  //转换为十进制
   return id;
}
//如ABC，
//第一趟A,id=0。
//第二趟B，id=0+1=1。
//第三趟C，id=1*26+2=28

如果字符串长度太大，则整数会太大，数组换空间时数组空间就会太大，所以长度不能太大。

同理，如果是小写字母，则视为整数26到51。

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');  //转换为十进制
      else if(S[i] >= 'a'&&S[i]<='z')
         id = id*52 + (S[i] - 'a') + 26; //转换为十进制还得加上前面大写字母的26
   }
   return id;
}
//如Abc，
//第一趟A,id=0。
//第二趟b，id=0*52+1+26=27。
//第三趟c，id=27*52+2+26。

而如果是数字，则有两种方法，一是把范围扩大到61，二是，如果前面字符是大写，并保证在字符串的末尾是数字，那就把前面的字母转换为十进制整数，再加上末尾的个数，就能有唯一的整数。如ABC4。

int hashFunc(char S[],int len){
   int id = 0;
   for(int i=0;i<len-1;i++){         //少一个长度
         id = id*26 + (S[i] - 'A');  //转换为十进制
   id=id*10 + S[i];                  //加上末尾数
   }
   return id;
}
//如ABC4，
//第一趟A,id=0。
//第二趟b，id=0*26+1=1。
//第三趟c，id=1*26+2=28。
//加上4，id=28*10+4=284

转换为hash问题：给出N个字符串（长度为3的大写字母），再给出M个查询字符串，问每个查询字符在N个字符串中出现的次数。

char S[100][5],temp[5];
int hashTable[26*26*26+1];
int hashFunc(char S[],int len){
   int id = 0;
   for(int i=0;i<len;i++)
      id = id*52 + (S[i] - 'A');  //转换为十进制
   return id;
}
int main(){
   int n,m;
   cin>>n>>m;
   for (int i = 0; i < n; i++)
   {
       cin >> x;
       hashTable[x]++;        //记录M在N中出现次数
   }
   for (int i = 0; i < m; i++)
   {
       cin >> x;
       cout <<hashTable[x]<<endl;  //输出次数
   }
   return 0;
}