如果一个符号表里所有的键都是小整数, 那么用数组存放无序的符号表, 其速度要快很多, 无论是插入还查找, 都是常数级别.
现实中的键不可能这么好, 所以需要一种方法, 就是将任意类型的键转换成一个范围内的索引.
此外还有一个问题, 就是不同的键转换成相同的索引, 这时候就会发生碰撞, 即两个实际上不同的键, 对应了同一个位置. 这个时候不能简单的覆盖值, 而需要采取其他的方法来进行存储数据, 有拉链法和线性探测法来解决这个问题.
散列表是典型的空间和时间互相替换的例子, 如果内存很大, 可以直接用二进制键来当成键; 如果时间很充分, 可以直接使用数组, 这样就无需使用额外空间.
散列表则通过数据结构的组合, 找到了一种
散列函数
散列, 就是把东西打散列出, 其实也就是任意给出一个键, 将其转换成一个整数范围内的值. 而且必须要散, 也就是平均. 来看一些常用的方法:
- 正整数, 正整数可以将其取余, 一般余数需要使用一个素数, 否则就会出现不平均的情况. 一般可以取一个离目标所需长度最接近的素数, 比如100长度的数组, 可以取97或者101.
- 浮点数, 其实浮点数本质也是一串二进制数, 如果将其乘以一些数字然后取余, 会导致不平均. 所以可以直接用二进制来除
- 字符串, 字符串在底层是一个char*指针, 但其实可以将字符串也当成数字, 即把其当成N位的R进制值, 然后除以一个素数并取余.
- 组合键, 如果键含有多个整型变量, 可以按一种方法也将其当成一串数字来进行操作
Java的基类Object里带有一个hashcode()方法, 其默认返回对象的内存地址, 但这个一般不太能行, 因为内存地址很可能会重复, 尤其是堆内存反复使用的过程中. 所以一些常用的数据类型, Java为其实现了不同的hashcode()方法, 比如String, Integer, Double, File, URL.
对于普通的默认返回内存地址的hashcode()的结果, 算法里提供了一个去除符号位然后取余的方法:
private int hash(Key key){
return (x.hashcode() & 0x7fffffff) % M
}
一般来说, 健壮的散列函数都是计算密集型的函数, 很耗费性能, 如果创建对象的时候直接计算, 效率不高. 所以Java里的hashcode会在第一次调用的时候计算散列值, 之后再调用就是缓存之后的散列值了.
基于拉链法的散列表
在有了散列函数之后, 下一步问题就是解决散列碰撞, 即实际不同的键, 经过散列函数计算出相同的值. 拉链法是一种解决方法, 即用一个链表存储相同散列值的键值对.
拉链实际上就是使用了一个指针数组, 每个元素指向一个数据结构用来保存多个键值对. 这里使用的数据结构是一个链表.
来看看散列表的实现:
public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n;
private int m;
private SequentialSearchST<Key, Value>[] st;
//构造函数, 使用INIT_CAPACITY传入有参构造函数, 实际上这个数字就是数组的长度
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}
//创建长度为m的链表数组
public SeparateChainingHashST(int m) {
this.m = m;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
}
//哈希函数, 除以m取余数
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
//取键值, 先找到对应的数组的索引, 再从链表中符号表中取出key
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
int i = hash(key);
return st[i].get(key);
}
//存入的时候同样先计算hash, 找到对应的链表, 再进行存储
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
//这里其实要调整数组的长度了, 目前可以先忽略
if (n >= 10*m) resize(2*m);
//计算hash值, 找到对应的链表, 然后存入值.
int i = hash(key);
if (!st[i].contains(key)) n++;
st[i].put(key, val);
}
}
这其中定义了一个初始的数量, 然后还有两个数值n和m, 初始数量实际上是数组长度, n用来记录这个表中存储的键值对的数量, m是链表的数量, 也就是将n个元素放入m个链表里, 所以要除以m来取余数.
从本质上看, 散列表其实是更加复杂的数据结构组合, 即符号表和数组的组合, 依赖hash计算数组的索引, 然后找到一个符号表, 调用这个符号表来存储真正的键值对.
基于线性探测法的散列表
线性探测法是开放地址散列表的一种. 所谓开放地址, 相对于上一节, 索引是什么, 就放入什么位置, 这种是闭合地址, 即一一对应. 开放地址指的是散列计算出来的索引, 键值不一定就存在那个索引位置, 而是使用数组中的空位来解决碰撞问题.
线性探测法解决碰撞的方法是:
- 命中, 键和被查找的键相同
- 不命中, 当前的键是null
- 不命中, 当前的键不是null, 继续向后查找. 找到就更新或者取数, 如果是插入操作, 直到找到null还没找到, 就存在null的地方
这个算法的本质是将null当做一块连续的区域的终点, 也是查找结束的标记. 如果在一个区域里没有找到对应的键, 那么就新增.
一个使用双数组的线性探测符号表如下:
public class LinearProbingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
//键值对总数
private int n;
//数组的长度, 两个数组一个存放键一个存放值
private int m;
private Key[] keys;
private Value[] vals;
//构造函数, 使用INIT_CAPACITY作为数组初始的长度
public LinearProbingHashST() {
this(INIT_CAPACITY);
}
public LinearProbingHashST(int capacity) {
m = capacity;
n = 0;
keys = (Key[]) new Object[m];
vals = (Value[]) new Object[m];
}
//插入函数
public void put(Key key, Value val) {
//依然是先判断键和值为空的情况
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
//如果已插入键值对的数量超过了数组长度的一半, 就扩充一倍的数组
if (n >= m/2) resize(2*m);
int i;
//计算键的hash值, 然后开始搜索直到null的位置.
for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
如果发现了键, 就更新值
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
//循环结束之后如果没找到, 则i停留在null的位置, 将当前键值插入的两个数组的i索引处
keys[i] = key;
vals[i] = val;
n++;
}
//查询函数
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
//与插入类似, 一样的循环, 在找到null之前如果找到了, 就返回对应的值
for (int i = hash(key); keys[i] != null; i = (i + 1) % m)
if (keys[i].equals(key))
return vals[i];
//for循环结束之后说明没找到, 返回null, 表明不存在该键
return null;
}
//删除函数
public void delete(Key key) {
//检测键是否为空和是否存在
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
if (!contains(key)) return;
//先找到对应的i索引
int i = hash(key);
while (!key.equals(keys[i])) {
i = (i + 1) % m;
}
//将两个数组对应的索引设置为空
keys[i] = null;
vals[i] = null;
//这一步操作很关键, 由于设置了为null, 就是一个搜索终点, 其后的元素如果不调整位置, 就不会被找到
i = (i + 1) % m;
//从i+1的位置向后不断寻找
while (keys[i] != null) {
//用临时变量保存键和值, 然后设置当前位置为null, 数量也减少1, 然后重新插入这个键
Key keyToRehash = keys[i];
Value valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + 1) % m;
}
//这个n--是删除要删除的元素的操作, 放到了最后, 在所有其后的元素重新插入完成之后, 再将总键值数量减少1
n--;
//删除之后也记得要调整大小
if (n > 0 && n <= m/8) resize(m/2);
assert check();
}
//所有键的队列实现, 比较简单, 挨个将不是null的Key放入Queue中, 返回这个Queue即可.
//由于Queue实现了迭代器, 所以可以对返回的Queue使用增强for循环
public Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < m; i++)
if (keys[i] != null) queue.enqueue(keys[i]);
return queue;
}
}
其他都是一些辅助函数, 可以看到, 其关键是在删除一个元素的同时, 将属于其后同一个查找组(叫做键簇)的元素全部重新插入符号表中.
使用线性探测符号表的话, 其数列长度是一个很重要的因素, 如果n=m, 会导致无限循环, 如果m远大于n, 则效率会好很多, 因为键簇既分散又小.
散列表的特点是:
- 很多时候是常数级别的插入和寻找操作
- 对键有要求, 每种类型的键都需要一个对应的散列函数
- 性能保证来自于散列函数的质量(还有散列表内部的存储空间)
- 虽然插入和寻找操作理论上耗时不多, 但散列函数可能是密集计算的性能杀手
- 难以实现有序的符号表
Java中的散列表有两种实现, java.util.TreeMap 是红黑树实现的符号表, java.util.HashMap 是散列表实现的符号表. 在实际中可以根据需要来取用.
