hash（散列）——思想、编码应用

散列

1，思想

引入：

直接把输入的数作为数组的下标来对这个数的性质进行统计

但是如果输入的范围大于10^9或是字符串，就不能将它们直接作为数组下标了。

核心思想：

将元素通过一个函数转为整数，使得该整数可以尽量唯一地代表这个元素。【这个函数就是散列函数】

即：如果一个元素在转换前为key，那么转换后就是一个整数H（key）

对于key是整数的情况，常用的方法有：直接定址法、平方取中法、除留余数法等

 

直接定址法就是直接把key作为数组下表，是最常用最实用的散列应用

 

或是线性变化（H(key)= a* key + b）

 

而平方取中法是取key的平方的中间若干位作为hash值（很少用）；

 

除留余数法是指把key除以一个数mod得到的余数作为hash值的方法，

即H（key） = key % mod

通过这个散列函数，可以把很大的数转换为不超过mod的函数，这样就可以将它作为可行的数组小标（⚠️：表长TSize必须不小于mod，不然会产生越界）

显然当mod是一个素数（质数）时，H（key）能尽可能覆盖[0,mod)范围内的每一个数。

因此一般为了方便起见，取TSize是一个素数，而mod直接取成与TSize相等。

 

2，冲突

当除留余数法产生两个及以上的H（key）时，这种情况称为“冲突”

解决冲突的方法：

1）线性探测法（Linear Probing）

当发生冲突时，检查下一个位置H(key) + 1是否被占用，如果没有就使用这个位置，否则继续检查下一个位置，直到找到一个可以使用过的位置，或者发现表中所有位置都已经被使用。（容易导致扎堆——表中连续若干位置都被使用）

 

2)平方探测法（Quadratic probing）

可以尽可能的避免扎堆现象，当表中下标为H（key）的位置被占时，将按下面的顺序检查表中的位置：

H（key）+ 1^2、H(key) - 1^2、H(key) + 2^2、H（key）-2^2、H（key）+3^2、…

若果检查过程中H(key)超过了表长TSize,那么就把H（key）+k^2对表长TSize取模；

若果检查过程中出现H(key)-k^2<0的情况（假设表的首位为0），那么将((H(key)-k^2)%TSize+TSize)%TSize作为结果（等价于将H(key)-k^2不断加上TSize直到出现第一个非负数。

如果想避免负数的麻烦，可以只进行正向的平方探测法。可以证明，如果k在[0,TSize]范围内都无法找到位置，那么当k>=TSzie，也一定无法找到位置

 

3)链地址法（拉链法）

链地址法不计算新的hash值，而是把所有的H（key）相同的key连接成一条单链表。

可以设定一个数组Link，范围时Link[0]~Link[mod]，其中Link[k]存放H（key）= h的一条单链表，于是当多个关键字key的hash值都是h时，就可以直接把这些冲突的key直接用单链表连接起来，此时就可以便利这条单链表来寻找所有H（key）= h的key。

 

3，字符串hash初步

这里重点在于讨论将一个字符串转换为唯一的整数。

先假设字符串都是又大写A～Z构成。不妨把A～Z视为0～25，这样就把26个大写字母对应到了二十六进制，这样就可以按照二十六进制转为十进制的思路，由进制转化的结论可知，得到的十进制时唯一的，由此便可以实现将字符串映射为整数的需求（转换为整数最大时26^len - 1, len为字符串长度）

int hashFunc(char S[], int len){

  int id = 0;

for (int i =0;i  < len; i++){

      Id = id * 26 +(S[i] - ‘A’);

    }

return id;

}

 

⚠️：如果字符串S的长度比较长，那么转换成的整数也会很大，因此使用时len不能太长。

如果字符串中出现了小写字母，那么可以把A～Z作为0～25，而把a～z作为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;

    }

  }

}

 

而如果出现了数字，一般有两种处理方法：

1）按照小写字母的处理方法，增大进制到62

2）如果保证在字符串的末尾时确定个数的数字，那么就可以把前面英文字母的部分按上面的思路转化为整数，再将末尾的数字直接拼接上去。

例如：字符串“BCD4”，可以把“BCD”转换为整数731，然后直接拼接上末尾的4变成7314即可。

示例代码：

int hashFunc(chat s[], int len){

  int id;

  for (int i = 0; i < len - 1; ++i)

  {

    id = id * 26 + (S[i] - 'A'); 

  }

  id = id * 10 + (S[len - 1] - '0');

  return id;

}

 

练习题目：

给出N个字符串，再给出M个查询字符串，问每个查询字符串子在N个字符串出现的次数。

 

#include<cstdio>

const int maxn = 100;

char S[maxn][5];

char temp[5];

int hastTable[26 * 26 * 26 +10];



int hashFunc(char S[], int len){

  int id = 0;

  for (int i = 0; i < len; ++i)

  {

    id = id * 26 + (S[i] - 'A');

  }

  return id;

}



int main(int argc, char const *argv[])

{

  int n, m;

  scanf("%d%d", &n, &m);

  for (int i = 0; i < n; ++i)

  {

    scanf("%s",S[i]);

    int id= hashFunc(S[i], 3);

    hastTable[id]++;

  }



  for (int i = 0; i < m; ++i)

  {

    scanf("%s", temp);

    int id = hashFunc(temp, 3);

    printf("%d\n", hastTable[id]);

  }

  return 0;

}