散列表(Hash Table)
1. 概述
散列表是使用散列函数,将相应的键值对映射到数组的某个位置的数据结构。
它在一般情况下相对于其他的数据结构要效率更高,你甚至可以实现在常数时间内进行查找和插入操作的符号表。
但是它也有相应的缺点,下面将会详细讲述
2. 散列函数
散列表一个重要部分就是散列函数的计算,我们使用散列函数将键值转换为数组的索引。
计算散列值一个很重要的方面就是让键值尽量分布到整个表中去,以避免碰撞的发生。
如果我们拥有一个大小为 的数组,那么我们需要返回 的散列值。
散列值的计算与类型相关。
2.1 Java 的约定
对于 Java 来说,比较幸运的是,Java 对于内置类型都实现了一个 hashCode()
方法,返回一个 32 位的 int
作为 hashCode
;
我们可以直接使用这个 hashCode
来实现我们自己的散列值计算。
需要注意的是,Java 要求如果 x
和 y
相等,那么它们两者的 hashCode
也相等。
2.2 散列计算方法
常用的散列方法是除留余数法。
我们选择大小为 的数组,对于任意的正整数 k,计算 k % M
,这样就能有效的将键分布于
最好选择使用质数。
虽然现在给不出严谨的数学证明,但是工程实践中说明使用质数作为除数可以更好地利用键值的信息。
2.3 使用 hashCode
的计算问题
下面是一个实现的例子:
private int hash(Key x) {
return (Math.abs(x.hashCode())) % M;
}
在这个例子中,因为 Java 的 hashCode
返回的是一个 int
值;
这说明 hashCode
的范围是 ;
但是我们需要的散列值要位于 ;
所以我们首先要将 hashCode
取绝对值。
通常来说,取绝对值一般使用 Math.abs()
;
但是,由于 hashCode
可以取到整个 32 位整形的范围;
当 hashCode
为 时,Math.abs()
是使用 -1
与之相乘;
此时,数值变为 ,出现 上溢,便会回绕至 ;
所以, 的绝对值是其本身!
正确的做法如下:
private int hash(Key x) {
return (x.hashCode() & 0x7fffffff) % M;
}
通过忽略整形中的符号位来达到取绝对值的作用。
2.4 浮点数
对于 0 到 1 浮点数,我们可以将它乘以 并四舍五入得到索引。
但是这种方法下,浮点数的高位作用更大,所以我们可以先将浮点数转为二进制数,随后使用除留余数法
2.5 字符串
对于字符串,我们也可以使用除留余数法。
通过 chatAt()
来返回一个 char
值。
以下的代码使用 Horner 算法来生成散列值
int hash = 0;
for (int i = 0; i < s.lengh(); i++) {
hash = (R * hash + s.charAt(i)) % M
}
2.6 组合键
如果键的类型含有多个整型变量,那么我们就可以将它们结合起来进行计算。
例如:
int hash = (((day * R + month) % M) * R + year) % M;
2.7 缓存
如果散列值的计算很耗时,那么我们或许可以将每个键的散列值缓存起来
Java 内置的 String
就使用了这种方法来减少计算量。
2.8 结论
为一个数据类型实现散列函数需要满足三个条件:
- 一致性——等价的键必定产生相等的散列值
- 高效性
- 均匀性
3. 碰撞处理
散列表的另一个重要部分是碰撞处理。
无论如何设计散列函数,总会出现两个不同的键得到同一个散列值的情况,这就叫做碰撞。
此时,我们就需要对碰撞进行处理。
3.1 拉链法
一种处理碰撞的方法就是拉链法,实际上就是使用链表储存碰撞的元素。
每个数组元素都是一个链表头,随后跟着与其碰撞的元素
此时,我们的数组大小 可以小于键值数量
3.1.1 实现
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 性能
- 在一张含有 条链表和 个键的散列表中,任意一条链表的键的数量均在 的常数范围内的概率无限趋向
- 在一张含有 条链表和 个键的散列表中,未命中查找和插入操作所需的比较次数为
这里可以看到,散列表的效率是很高的,一般情况下只需要常数级别的时间即可完成搜索和插入
3.2 开放地址法
另一种碰撞处理方法啊就是开放地址法,它倾向于利用数组中的空位来解决冲突。
所以如果使用这种方法来进行碰撞处理,那么就要求数组的数量 大于键值数量 。
3.2.1 实现
开放地址的最简单实现叫做线性探测法:当碰撞发生时,直接检查数组的下一个位置。
这会产生三种结果:
- 命中
- 未命中(为空)
- 未命中(该位置的键与被查找的键不同)
特别重要的一点是,我们要在到达数组结尾时返回开头。
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 性能
在一张大小为 并含有 个键的基于线性探测的散列表中,命中和未命中的查找所需要的探测次数分别为:
所以,如果要维护线性探测法的最佳性能;
应尽量保证数组是半满的
4. 结论
-
散列表在一般情况下可以实现常数级别的查找和插入操作
-
性能保证来自于散列函数的质量
这会导致散列表性能的不稳定,同时容易受到外部攻击。
一些特殊的数据在经过散列计算后会映射到同一个位置,此时散列表的性能就会急剧下降。当需要性能保证时,优先考虑平衡二叉树(红黑树)
-
散列计算可能复杂而且昂贵
-
难以支持有序性相关的符号表操作
经过散列计算后,键值对会随机地分布于数组中,不能保持其插入顺序。