(本文转载,自己做了少许修正,若有侵权请联系删除)

简单了解散列(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。

img

字符串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;
}

如果出现了数字,一般有两种解决方法,

  1. 按照上述方法,增加进制到62;
  2. 如果末位确定是个数字,那么前面的字母转化成整数后直接拼接上这个数字,例如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;
}

参照资料

五分钟搞定散列(hash)算法思想

hash表拉链法解决冲突