散列的定义与整数散列

问题提出：给出 N 个正整数，再给出 M 个正整数，问这 M 个数中的每个数分别是否在 N 个数中出现过，其中 N ，M ≤ 10^5，且所有正整数均不超过 10^5。

直观的思路是：对每个欲查询的正整数 x ，遍历所有 N 个数，看是否有一个数与 x 相等。这种做法的时间复杂度为 O(NM)，当 N 和 M 都很大（10^5 级别）时，显然是无法接受的。

用空间换时间的做法：设定一个 bool 型数组hashTable[100010]，其中hashTable[x] == true表示正整数 x 在 N 个正整数中出现过，而hashTable[x] == false表示正整数 x 在 N 个正整数中没有出现过。这样就可以在一开始读入 N 个正整数时就进行预处理，即当读入的数为 x 时，就令 hashTable[x] = true。于是对 M 个欲查询的数，就能直接通过hashTable数组判断出每个数是否出现过。显然这种做法的时间复杂度为 O(N + M) 。

直接把输入的数作为数组的下标来对这个数的性质进行统计。这是一个很好的用空间换时间的策略，因为它将查询的复杂度降到了 O(1) 级别。但是该策略存在一个局限性，出现数的大小不会超过 10^5。如果输入可能是 10^9 大小，或者甚至是一个字符串，就不能将它们直接作为数组下标。

散列的存在，就是将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素。其中把这个转换函数称为散列函数 H，也就是说，如果元素在转换前为 key，那么转换后就是一个整数 H(key)。

常用散列函数

• 直接定址法。恒等变换，H(key) = key；线性变换，H(key) = a * key + b。
• 平方取中法。取 key 的平方的中间若干位作为 hash 值（很少用）。
• 除留余数法。把 key 除以一个数 mod 得到的余数作为 hash 值，H(key) = key % mod较常用）。

有时候使用散列函数，可能会发生冲突，即两个不同的数 key1 和 key2，它们的 hash 值 H(key1) 与 H(key2) 是相同的。

解决冲突

• 线性探查法
  当得到 key 的 hash 值 H(key)，但是表中下标为 H(key) 的位置已经被其他某个其他元素使用了，那么久检查下一个位置 H(key) + 1 是否被占，如果没有，就使用这个位置；否则就继续检查下一个位置（H(key) + 2）。如果检查位置超过了表长，就回到表首继续循环，直到找到一个可以使用的位置，或者发现表中所有位置都已被占用。
  缺点：容易扎堆，即表中连续若干位置都被使用。
• 平方探查法
  为了尽可能避免扎堆现象，当表中下标为 H(key) 的位置被占时，将按下面的顺序检查表中的位置：H(key) + 1^2、H(key) - 1^2、H(key) + 2^2、H(key) - 2^2、H(key) + 3^2...。如果 H(key) + k^2 超过了表长 TSize ，就把 H(key) + k^2 对表长 TSize 取模；如果 H(key) - k^2 < 0，就计算 ((H(key) - k^2) % TSize + TSize) % Tsize，等价于将 H(key) - k^2 不断加上 TSize 直到出现第一个非负数。
• 链地址法
  链地址法不计算 hash 值，而是把所有 H(key) 相同的 key 连接成一条单链表。这样可以设定一个数组 Link ，范围是 Link[0] ~ Link[mod - 1] ，其中 Link[h] 存放 H(key) = h 的一条单链表，于是当多个关键字 key 的 hash 值都是 h 时，就可以把这些冲突的 key 直接用单链表连接起来。最后可以直接遍历这条单链表来寻找所有 H(key) = h 的 key。

二维整数

如何将一个二维整点 P 的坐标映射为一个整数，使得该整点 P 可以由该整数惟一地代表？
假设一个整点 P 的坐标是 (x, y)，其中 0 ≤ x,y ≤ Range，那么可以令 hash 函数为 HP = x * Range + y 。这样对数据范围内任意两个整点 P1 和 P2 ，H(P1) 都不会等于 H(P2) ，可以用 H(P) 来唯一地代表点 P，接着可以使用整数 hash 的方法进一步映射到较小的范围。

字符串 hash 初步

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

假设字符串均由大写字母 A ~ Z 组成，那么把 A ~ Z 视为 0 ~ 25，这样就把 26 个大写字母对应到了二十六进制中。接着将二十六进制转换为十进制，得到的结果肯定是惟一的，由此便实现了将字符串映射为整数的需求。
同理，如果有小写字母，就把 a ~ z 视为 26 ~ 51，这样就变成了五十二进制转换为十进制的问题。
如果出现了数字，可以增大进制数至六十二。

给出 N 个字符串（均由三位大写字母组成），再给出 M 个查询字符串，问每个查询字符串分别在 N 个字符串中出现的次数。

#include <iostream>
using namespace std;

const int maxn = 100;
char S[maxn][5], temp[5];
int hashTable[26 * 26 * 26 + 10];

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

int main(int argc, char** argv) {
    
    int n, m;
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        cin>>S[i];
        int id = hashFunc(S[i], 3);  //将字符串 S[i] 转换为整数 
        hashTable[id]++;  //该字符串的出现次数加 1 
    }
    
    for(int i=0; i<m; i++){
        cin >> temp;
        int id = hashFunc(temp, 3);  //将字符串 temp 转换为整数 
        cout<<hashTable[id];  //输出该字符串的出现次数 
    }
    
    return 0;
}

// 测试结果
6 3                      //输入 n，m 值
WER ABC OJK ABC RET POD  //输入 n 个字符串
WEU ABC POD              //输入 m 个字符串
021                      //输出 m 个字符串分别在 n 个字符串中出现的次数