算法笔记 散列

本文将介绍散列 (hash) 这一常见的算法思想。

一、用空间换时间

先看一个简单的问题：给出 N 个正整数，再给出 M 个正整数，问这 M 个数中的每个数分别是否在 N 个数中出现过，其中 N, M <= 105 ，且所有正整数均不超过 105 。例如 N=5，M=3，N 个正整数为 {8, 3, 7, 6, 2}，欲查询的 M 个正整数为 {7, 4, 2}，于是后者中只有 7, 2 在 N 个正整数中出现过。

对于这个问题，最直观的思路是：对每个欲查询的正整数 x，遍历所有 N 个数，看是否由一个数与 x 相等。这种做法的时间复杂度为 o(NM) ，当 N 和 M 都很大时，显然是无法承受的。

还有另一个办法，用空间换时间 。即设定一个 bool 型数组 hashTable[100010] ，并先全部初始化为 false ，再遍历 N 个正整数对 bool 数据进行预处理。其中 hashTable[x] == true 则表示正整数 x 在 N 个数中出现过，反之则表示正整数 x 在 N 个正整数中没有出现过。之后再依次读入 M 个正整数，若 hashTable[x] == true 说明可以查询到，否则则不行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
const int maxn = 100010;
bool hashTable[maxn] = {false};
int main(){
	int i, n, m, x;
	scanf("%d %d", &n, &m);
	// 预处理,确定哪个数字在N中出现过
	for (i = 0; i < n; i++){
		scanf("%d", &x);
		hashTable[x] = true;
	}
	// 判断M中的元素是否在N中出现过
	for (i = 0; i < m; i++){
		scanf("%d", &x);
		if (hashTable[x] == true)  printf("YES\n");
		else  printf("NO\n");
	}
	return 0;
}

如果题目要求得到欲查询数在 N 中出现的次数，需要对预处理代码做以下改动。

1
2
3
4
5
6
7
······
int hashTable[maxn] = {0};
······
for (i = 0; i < n; i++){
    scanf("%d", &x);
    hashTable[x]++;
}

​

二、散列

1.散列的概念

上面的做法有一个特点，那就是直接把输入的数作为数组的下标来进行统计运算。这时一个很好的策略，但存在可以优化的地方——如果数字是庞大的天文数字，或者甚至是一个字符串，就不能把它们作为数组下标。

散列 (Hash) 就是用来解决这个问题的，它可以用一句话概括： 将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素 。

2.常用 Hash 函数

对于 key 是整数的情况，常用的 hash 函数有直接定址法、数字分析法、平方取中法、除留余数法等。

(1) 直接定址法

1
2
3
H(key) = key
或
H(key) = a * key + b

(2) 数字分析法

选取关键字中的若干数位组成 Hash 地址，选取的原则是尽量减少冲突。

(3) 平方取中法

将关键字平方，选择平方结果中的部分数位。

(4) 除留余数法

将 key 除以一个数 mod 得到的余数作为 hash 值。

1
H(key) = key % mod

  • mod 应该小于等于 hash 表的长度 length 。（否则就放不进去）

  • mod 选取素数，能够更好地防止冲突。

  • mod 应尽可能大，以避免空间的浪费。

综上，mod 一般选取小于等于表长的最大素数。

3.冲突的处理

在 hash 表中，若 H(key1) == H(key2) ，即不同的数据经计算后得出相同的结果，因此也理应放入同一个地方，便称为发生了冲突。冲突无法完全避免，只能尽量减少冲突的发生，因此在建立 hash 表时就必须考虑冲突处理。

常见的冲突处理方法有：

(1) 线性探查法

依次检查下一个位置，找到空位时就将关键字放入。

(2) 平方探查法

依次检查 H(key)+1 、 H(key)-1 、 H(key)+4 、H(key)-4 、H(key)+9 ······，找到空位后将关键字放入。

(3) 链地址法

将所有同义词用单链表串联起来。 hash 表中不再存放记录本身，而是存放指向相应链表的指针。

​

三、二维坐标的 hash 函数

如果 key 不是整数，应该如何设计散列函数？

一个例子是：如何将一个二位整点 P 的坐标映射为一个整数，使得整点 P 可以由该整数唯一地代表。假设一个整点的坐标是 (x, y) ，其中 0 <= x, y < Range ，那么可以令 hash 函数为 H(P) = X * Range + y ，这样数据范围内地任意一个整点都一定只有唯一的 hash 函数值。

当 0 <= x, y < Range 时，hash 函数值一定由 n 个 Range 和 一个小于 Range 的数组成，可以很容易地唯一确定一个函数值。

原书：

假设一个整点的坐标是 (x, y) ，其中 0 <= x, y <= Range ，那么可以令 hash 函数为 H(P) = X * Range + y ，这样数据范围内地任意一个整点都一定只有唯一的 hash 函数值。

这里有一个问题， (n, Range) 的函数值会与 (n + 1, 0) 重合，导致冲突。

​

四、字符串的 hash 函数

字符串 hash 是指将一个字符串 S 映射为一个整数，使得该整数可以尽可能唯一地代表该字符串。此处只讨论将字符串转换为唯一的整数。为讨论方便，先假设字符串均由大写字母 AZ 构成，并把 AZ 视为 0~25 ，于是字符串就可以转换为二十六进制数，

BZA

01 25 00

接着，按照将二十六进制转换为十进制的思路，将字符串转换为“对应的十进制数”。因为字符串对应的二十六进制数，其数组都是一一对应且不重合的，因此将其转换为十进制后，也是一一对应且不重合的。由此便可实现将字符串映射为整数的需求。代码如下：

1
2
3
4
5
6
7
8
int hash(char S[], int len){
	int i;
	int id = 0;
	for (i = 0; i < len; i++){
		id = id * 26 + S[i] - 'A';
	}
	return id;
}

如果字符串中出现了小写字母，可以把 az 看作 2651 ，将问题变成五十二进制转化为十进制的问题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
int hash(char S[], int len){
	int i;
	int id = 0;
	for (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;
	}
	return id;
}

如果字符串中出现数字，一般由两种处理方法：

  • 按照小写字母的处理方法，增大进制数至62。

  • 如果保证在字符串的末尾是确定个数的数字，那么就可以把前面英文字母部分先转换为整数，再直接把末尾的数字拼接上去。

例如：

BCD4

① 先将 BCD 转换为整数 731

② 将 4 拼接上去

③ 如上，H(BCD4) = 7314

​

参考

  • 算法笔记