【Algorithms公开课学习笔记11】 符号表part4——哈希表
哈希表HashTable
0.前言
前面的文章我们分析了符号表的集中实现方式:有序链表、无序数组、二叉搜索树(BST)、平衡搜索树(红黑树法)等,通过下图回忆一下各种实现方法的性能对比。
那么,除此之外,是否还存在性能更好的实现方法呢?答案是肯定的,就是本文将重点介绍的哈希表(HashTable)。
1.哈希函数
哈希表就是使用一个key-indexed的表来存储数据,其中该index是对key使用哈希函数计算的结果。(如下图所示)
哈希存在以下三个注意事项:
- 哈希容易运算
- 相等性检测:能够通过哈希运算检测两个输入值是否相等
- 冲突解决:能够解决哈希冲突的情况。哈希冲突是指当两个不同的输入经过哈希运算的结果相同的index时
所以,哈希函数的目标是:均匀地为每一个key产生一个index,具体体现在:
- 高效的运算
- 一个index等可能地服务于一个key(理想情况下,一个key只产生一个index)
hashCode
在Java中,每一个类都继承了hashCode()方法,该方法会返回一个32bit的整型数据。
默认情况下,hashCode(x)返回的是x在内存中的地址,用户可以通过重写hashCode()方法改变这一规则。在Java库里,hashCode()的实现如下:
//Integer,整型本身就可以作为index,故返回本身
public final class Integer{
private final int value;
...
public int hashCode(){
return value; }
}
//Boolean,布尔值只有两种情况,故只需返回两个index
public final class Boolean{
private final boolean value;
...
public int hashCode(){
if (value) return 1231;
else return 1237;
}
}
//Double
public final class Double{
private final double value;
...
//先转成64bit的形式,然后进行位异或,最后返回强转整型的index值
public int hashCode(){
long bits = doubleToLongBits(value);
return (int) (bits ^ (bits >>> 32));
}
}
//String,先将字符串拆成字符数组,然后使用公式:h = s[0]·31^L–1+ … +s[L–3]·312 +s[L–2]·31^1 +s[L–1]·31^0.
public final class String{
//为了方便,可以先将结果缓存(因为String是immutable的)
private int hash = 0;
private final char[] s;
...
public int hashCode(){
int h = hash;
if (h != 0) return h;
for (int i = 0; i < length(); i++)
hash = s[i] + (31 * hash);
hash = h;
return hash;
}
}
对于用户自定义的类中,可以使用以下标准来重写hashCode()方法:
- 对每一个有意义的域使用x=31x+y的规则
- 如果域是基本类型(int, float等),则使用其包装类的hashCode()方法
- 如果域是null,则返回0
- 如果域是引用类型,则使用hashCode()方法
- 如果域是数组,则对每一个数组项使用hashCode()方法(或者使用Arrays.deepHashCode()方法)
//用户自定义类型
public final class Transaction implements Comparable<Transaction>{
private final String who;
private final Date when;
private final double amount;
public Transaction(String who, Date when, double amount){ /* as before */ }
...
public boolean equals(Object y){ /* as before */ }
public int hashCode(){
//非零常数
int hash = 17;
//引用类型
hash = 31*hash + who.hashCode();
hash = 31*hash + when.hashCode();
//基本类型
hash = 31*hash + ((Double) amount).hashCode();
return hash;
}
}
前文讲到hashCode()返回一个32位的整型数据,其范围是:-2^31 ~ 2^31 -1。
- 由于我们哈希的目的是得出index,如果数组的长度为M,则index只能取0 ~ M-1之间的值。这时,对hashCode()的结果对M取模即可。
- 由于index的值均为正整数,而hashCode()的结果存在负数,故需要将其转化成正数。不能直接使用Math类的绝对值方法,因为有可能会使-2^31 变成2^31而越界。这时,可以让hashCode()结果位与0x7fffffff。
//错误,可能会越界
private int hash(Key key){
return Math.abs(key.hashCode()) % M;
}
//符合实际需求的哈希函数
private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
均匀哈希假想(Uniform hashing assumption)
均匀哈希假想:每一个key值都等可能地哈希成一个0 ~ M-1的整型值。
设想一个球与桶的模型:随机地往M个桶抛球,存在以下情况:
Birthday problem:经过 ~sqrt(πM /2)次投掷后,会出现两个球进入同一个桶的情况(首次出现冲突)
Coupon collector:经过 ~MlnM 次投掷后,每一个桶至少有一个球(所有桶都有球)
Load balancing:经过 M次投掷后,大多数loaded的桶会有Θ(logM / log logM)个球
因此,如果满足均匀哈希假想的场景,将满足上述的三种情况。
2.哈希冲突之分链法(separate chaining)
上文已经涉及了哈希冲突,所谓哈希冲突是指当两个不同的输入key经过哈希运算后出现相同的index的情况。
处理哈希冲突有两个常用的方法:分链法和线性探测。本小节介绍分链法,线性探测法将在下一小节分析。
分链法
分链法是使用size为M的数组来存放index,且每个index将指向一条链表。基本操作如下:
- 哈希:将key映射成0 ~ M-1的整数i
- 插入:将该key-vaule对插入第i条链表,每条链表有数组索引
- 查找:根据key的映射整数i查找到第i条链表,然后在链表中使用key来匹配查找value值
public class SeparateChainingHashST<Key, Value>{
private int M = 97; //数组大小,即链表的数量
private Node[] st = new Node[M]; //数组
//链表节点
private static class Node{
private Object key;
private Object val;
private Node next;
...
}
//哈希操作
private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
//插入操作
public void put(Key key, Value val) {
int i = hash(key);
for (Node x = st[i]; x != null; x = x.next)
if (key.equals(x.key)){
x.val = val;
return;
}
st[i] = new Node(key, val, st[i]);
}
//查找操作
public Value get(Key key) {
int i = hash(key);
for (Node x = st[i]; x != null; x = x.next)
if (key.equals(x.key))
return (Value) x.val;
return null;
}
}
性能分析
在分链法中,会影响时间性能的就是参数M的选择了。实验证明,在均匀哈希假想下,链表的key的个数是N/M的概率接近于1,因此,链表大小的分布的服从二项分布的。
因此,M的大小就很关键了。如果M过大,就会出现许多短链,甚至空链;如果M过小,就会出现长链。理论上,M的最佳值为M ~ N/5,即N/M = 5。
分链法的时间性能如下。其中平均情况是满足均匀哈希假想下成立的
3.哈希冲突之线性探测(linear probing)
本节我们继续分析哈希冲突的另一个解决方法——线性探测法。
线性探测法
线性探测法采用的措施是:用size为M的数组来存储N个数据时,如果产生冲突,就寻找下一个空项来存储(M必须大于N)。基本操作如下:
- 哈希:将key映射成0 ~ M-1的整数i
- 插入:将key插入到位置i,如果冲突,就往下位置i+1, i+2……
- 查找:从位置i取出key-value对,如果key存在但不匹配,就往下位置i+1, i+2……
public class LinearProbingHashST<Key, Value>{
private int M = 30001; //M必须足够大,大于N
private Value[] vals = (Value[]) new Object[M];//数组不能泛型
private Key[] keys = (Key[]) new Object[M];
//哈希操作
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
//插入操作
public void put(Key key, Value val){
int i;
for (i = hash(key); keys[i] != null; i = (i+1) % M)
if (keys[i].equals(key))
break;
keys[i] = key;
vals[i] = val;
}
//查找操作
public Value get(Key key){
for (int i = hash(key); keys[i] != null; i = (i+1) % M)
if (key.equals(keys[i]))
return vals[i];
return null;
}
}
knuth’s parking问题
问题模型:在一条单向的路上有M个停车位,每一台车都是随机寻找停车位i,如果i已经被占用,就往下寻找i+1,i+2……。问:如何计算一辆车在parking过程中的平均位移(mean displacement)。
半满half-full:当已经停有M/2辆车时,平均位移 ~ 3/2
全满full:当已经停有M辆车时,平均位移 ~ sqar(πM /8)
将knuth’s parking问题类比到线性探测法中同样适用。因此,在线性探测法中,同样要注意M值对时间性能的影响。
性能分析
在均匀哈希假想下,如果N/M = α时,查找一个key值一次命中与不命中的概率如下图,数学证明略。
当M值过大时,数组就会有许多空项,浪费空间;当M值过小时,就会有许多冲突,查找的时间就会剧增。理论证明,α值最佳为 ~1/2,根据N/M = α,可以计算出最佳M值。
线性探测法的时间性能如下。其中平均情况是满足均匀哈希假想下成立的
4.其他
单向哈希函数
由于哈希会发生冲突,恶意对手可以通过研究你的哈希函数来确定发生冲突的case,然后制造大量冲突的块去堵塞通道(如果你采用分链法,就会出现某条链特别长),从而影响系统性能,甚至导致系统瘫痪。这种称为拒绝服务攻击。
在Java1.1版本中,String型的hashCode()就存在以下已知的冲突:
因此,有人就提出了单向哈希函数(one-way hash function),单向哈希函数的特征是容易通过key哈希得到index,但是通过index反向找到应该哈希的key是很困难的。
在实际应用中,MD5, SHA-0, SHA-1, SHA-2都是安全性达到要求的哈希函数。哈希函数通常可用于数字签名、密码存储、消息认证等场景。
分链法vs线性探测法
分链法
- 比较容易去实现delete方法,但要注意哈希表是不支持其他ordered operation的
- 能够优雅地降低性能,即降低性能的同时实现起来也简单
- 对聚簇的影响不敏感,更关注对哈希函数的设计
线性探测法
- 更节约空间
- 更好的缓存特性
优化的哈希函数
双探头哈希Two-probe hashing
双探头哈希是分链法的进化型。它会用两个哈希函数将key哈希到两个位置,然后选择链比较短的那条进行存放。有效地将最长链的长度减小到理想中的log logN。
双重哈希Double hashing
双重哈希是线性探测法的进化型。它使用线性探测,在发生冲突时,不是一个个往下找,而是间隔若干个往下找。这样可以有效地消除聚簇的影响,并且能够让哈希表接近full的状态。但是删除操作不容易实现。
Cuckoo hashing
Cuckoo hashing是线性探测的进化型。它会用一个哈希函数将key哈希到两个位置,随机选择一个存储。如果第一个位置已被占用,就选择另一个位置存储之。
哈希表vs平衡搜索树
哈希表
- 容易实现,但不支持ordered operation
- 对于简单的key,性能表现得更好
- 对于无序的key,暂无有效的替代品(不理解)
- 在Java中,java.util.HashMap, java.util.IdentityHashMap 都是通过哈希表实现的
平衡搜索树
- 有更强的性能保证(哈希表要在均匀哈希假想的前提下,而BSTs无需前提)
- 支持order operation
- 相比于实现equal()和hashCode(),实现compareTo()更容易
- 在Java中,java.util.TreeMap, java.util.TreeSet 都是通过BSTs实现的