(本文转载,自己做了少许修正,若有侵权请联系删除)
简单了解散列(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;
}