散列表(Hash Table)

1. 概述

散列表是使用散列函数,将相应的键值对映射到数组的某个位置的数据结构。

它在一般情况下相对于其他的数据结构要效率更高,你甚至可以实现在常数时间内进行查找和插入操作的符号表。

但是它也有相应的缺点,下面将会详细讲述

2. 散列函数

散列表一个重要部分就是散列函数的计算,我们使用散列函数将键值转换为数组的索引。

计算散列值一个很重要的方面就是让键值尽量分布到整个表中去,以避免碰撞的发生。

如果我们拥有一个大小为 MM 的数组,那么我们需要返回[0,M1][0, M - 1] 的散列值。

散列值的计算与类型相关。

2.1 Java 的约定

对于 Java 来说,比较幸运的是,Java 对于内置类型都实现了一个 hashCode() 方法,返回一个 32 位的 int 作为 hashCode

我们可以直接使用这个 hashCode 来实现我们自己的散列值计算。

需要注意的是,Java 要求如果 xy 相等,那么它们两者的 hashCode 也相等。

2.2 散列计算方法

常用的散列方法是除留余数法

我们选择大小为 MM 的数组,对于任意的正整数 k,计算 k % M,这样就能有效的将键分布于 [0,M1][0, M - 1]

MM 最好选择使用质数

虽然现在给不出严谨的数学证明,但是工程实践中说明使用质数作为除数可以更好地利用键值的信息。

2.3 使用 hashCode 的计算问题

下面是一个实现的例子:

1
2
3
private int hash(Key x) {
return (Math.abs(x.hashCode())) % M;
}

在这个例子中,因为 Java 的 hashCode 返回的是一个 int 值;

这说明 hashCode 的范围是 2312311-2^{31} \sim 2^{31} - 1

但是我们需要的散列值要位于 [0,M1][0, M - 1]

所以我们首先要将 hashCode 取绝对值。

通常来说,取绝对值一般使用 Math.abs()

但是,由于 hashCode 可以取到整个 32 位整形的范围;

hashCode231-2^{31} 时,Math.abs() 是使用 -1 与之相乘;

此时,数值变为 2312^{31},出现 上溢,便会回绕至 231-2^{31}

所以,231-2^{31} 的绝对值是其本身!

正确的做法如下:

1
2
3
private int hash(Key x) {
return (x.hashCode() & 0x7fffffff) % M;
}

通过忽略整形中的符号位来达到取绝对值的作用。

2.4 浮点数

对于 0 到 1 浮点数,我们可以将它乘以 MM 并四舍五入得到索引。

但是这种方法下,浮点数的高位作用更大,所以我们可以先将浮点数转为二进制数,随后使用除留余数法

2.5 字符串

对于字符串,我们也可以使用除留余数法。

通过 chatAt() 来返回一个 char 值。

以下的代码使用 Horner 算法来生成散列值

1
2
3
4
int hash = 0;
for (int i = 0; i < s.lengh(); i++) {
hash = (R * hash + s.charAt(i)) % M
}

2.6 组合键

如果键的类型含有多个整型变量,那么我们就可以将它们结合起来进行计算。

例如:

1
int hash = (((day * R + month) % M) * R + year) % M;

2.7 缓存

如果散列值的计算很耗时,那么我们或许可以将每个键的散列值缓存起来

Java 内置的 String 就使用了这种方法来减少计算量。

2.8 结论

为一个数据类型实现散列函数需要满足三个条件:

  1. 一致性——等价的键必定产生相等的散列值
  2. 高效性
  3. 均匀性

3. 碰撞处理

散列表的另一个重要部分是碰撞处理

无论如何设计散列函数,总会出现两个不同的键得到同一个散列值的情况,这就叫做碰撞

此时,我们就需要对碰撞进行处理。

3.1 拉链法

一种处理碰撞的方法就是拉链法,实际上就是使用链表储存碰撞的元素

每个数组元素都是一个链表头,随后跟着与其碰撞的元素

此时,我们的数组大小 MM 可以小于键值数量 NN

3.1.1 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class SeparateChainingHashST<Key, Value> {
private int N; // 键值对总数
private int M; // 散列表的大小
private SequentialSearchST<Key, Value>[] st; // 存放链表的数组

public SeparateChainingHashST() {
this(997);
}

public SeparateChainingHashST(int M) {
// Create linked list
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];

for (int i = 0; i < M; i++) {
st[i] = new SequentialSearchST();
}
}

private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}

private Value get(Key key) {
return (Value) st[hash(key)].get(key);
}

private void put(key, val) {
st[hash(key)].put(key, val);
}
}

关于删除操作,拉链法的删除操作相对简单,只需要找到 SequentialSearchST 对象,直接调用 delete() 方法即可。
实际上就是链表的删除操作。

3.1.2 性能

  1. 在一张含有 MM 条链表和 NN 个键的散列表中,任意一条链表的键的数量均在 N/MN/M 的常数范围内的概率无限趋向 11
  2. 在一张含有 MM 条链表和 NN 个键的散列表中,未命中查找和插入操作所需的比较次数为 N/M\sim N/M

这里可以看到,散列表的效率是很高的,一般情况下只需要常数级别的时间即可完成搜索和插入

3.2 开放地址法

另一种碰撞处理方法啊就是开放地址法,它倾向于利用数组中的空位来解决冲突。

所以如果使用这种方法来进行碰撞处理,那么就要求数组的数量 MM 大于键值数量 NN

3.2.1 实现

开放地址的最简单实现叫做线性探测法:当碰撞发生时,直接检查数组的下一个位置。

这会产生三种结果:

  1. 命中
  2. 未命中(为空)
  3. 未命中(该位置的键与被查找的键不同)

特别重要的一点是,我们要在到达数组结尾时返回开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class LinearProbingHashST<Key, Value> {
private int N;
private int M;
private Key[] keys;
private Value[] vals;

public LinearProbingHashST() {
keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];
}

private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}

private void resize() [
/* resize method*/
}

public put(Key key, Value val) {
if (N >= M / 2) resize(2 * M);

int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}

keys[i] = key;
vals[i] = val;
N++;
}

public Value get(Key key) {
for (int i = hash(key); keys[i] != nul; i = (i + 1) % M) {
if (keys[i].equals(key)) {
return vals[i];
}
}
return null;
}

public void delete(Key key) {
if (!contains(key)) {
return;
}

int i = hash(key);

while(!key.equals(keys[i])) {
i = (i + 1) % M;
}
keys[i] = null;
vals[i] = null;

i = (i + 1) % M;
while (keys[i] != null) {
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo, valToRedo);
i = (i + 1) % M;
}
N --;

if (N > 0 && N == M / 8) resize(M /2);
}
}

关于删除操作:
我们不能直接将键的位置设置为 null,这会导致剩下的键无法被找到,所以我们需要将被删除键的右侧的键重新插入

3.2.2 性能

在一张大小为 MM 并含有 N=αMN = \alpha M 个键的基于线性探测的散列表中,命中和未命中的查找所需要的探测次数分别为:

12(1+11a)\sim \frac{1}{2}(1 + \frac{1}{1 - a})

12(1+1(1a)2)\sim \frac{1}{2}(1 + \frac{1}{(1 - a)^2})

所以,如果要维护线性探测法的最佳性能;

应尽量保证数组是半满

4. 结论

  1. 散列表在一般情况下可以实现常数级别的查找和插入操作

  2. 性能保证来自于散列函数的质量

    这会导致散列表性能的不稳定,同时容易受到外部攻击。
    一些特殊的数据在经过散列计算后会映射到同一个位置,此时散列表的性能就会急剧下降。

    当需要性能保证时,优先考虑平衡二叉树(红黑树)

  3. 散列计算可能复杂而且昂贵

  4. 难以支持有序性相关的符号表操作

    经过散列计算后,键值对会随机地分布于数组中,不能保持其插入顺序。