散列的定义与整数散列
问题提出:给出 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 个字符串中出现的次数
网友评论