哈希表检索的实现
哈希函数
哈希函数是一种从任何一种数据中创建小的数字“指纹”的方法。这样,我们就可以将关键码映射为存储索引,检索时只需计算出给定值的哈希值,就可以像顺序表那样找到对应记录。
除余法
用关键码 x 除以 M (往往取散列表长度,取素数),并取余数作为哈希值
连续的关键码会映射成连续的哈希值,这样保证了连续的关键码不发生冲突,但是会占据连续的数组单元,导致哈希性能的降低
乘余取整法
$hash(key)=\lfloor n\times ((A\times key)\%1) \rfloor$,其中 $\%1$ 表示取小数部分,$0<A<1$ 一般取黄金分割最理想
平方取中法
先通过求关键码的平方来扩大差别,再取其中的几位或其组合作为哈希值
数字分析法
因为哈希函数的目标是尽可能让哈希值在其范围上分布均匀,以减少冲突的发生,所以可以取那些分布均匀的位作为哈希值
设有 $n$ 个 $d$ 位数,每一位可能有 $r$ 种不同的符号,定义第$k$位的均匀度 \(\lambda_k=\sum_{i=1}^r(\alpha_i^k-\frac{n}{r})^2\) $\alpha_i^k$表示第 $i$ 个符号在第 $k$ 位上出现的次数,$\frac{n}{r}$ 表示各种符号在$n$个数中均匀出现的期望值,由这个指标,我们可以选择某些均匀度小(分布均匀)的位作为哈希值
缺点是在关键码变化后需要重新计算
基数转换法
把关键码看成是另一进制上的数后,再把它转换成原来进制上的数,取其中若干位作为散列地址,一般取大于原来基数的数作为转换的基数,并且两个基数要互素
折叠法
关键码所含的位数很多,采用平方取中法计算太复杂,就可以使用折叠法
将关键码分割成位数相同的几部分(最后一部分可以不同)
- 把各部分的最后一位对齐相加,这就是移位叠加
- 各部分不分割,沿各部分的分界来回折叠,然后对齐相加,这就是分界叠加
ELF字符串散列函数
int ELFhash(char* key) {
unsigned long h = 0;
while(*key) {
h = (h << 4) + *key++;
unsigned long g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h % M;
}
哈希函数碰撞的处理
开散列-拉链法
对哈希碰撞的元素以链表的形式保存,Java中的HashMap
就是采用这种策略。
闭散列
当冲突发生时,使用某种方法为关键码生成一个探查序列,从序列中选择一个空的位置插入
- 线性探查:如果记录的基位置存储位置被占用,那么就在表中移动常数个位置,直到找到一个空存储位置
- 二次探查:取探查的增量序列为 $1^2,-1^2,2^2,-2^2,\cdots$,避免了基本聚集
- 伪随机数序列探查:取探查的增量为伪随机数序列的值,避免了基本聚集
- 双散列探查:去探查的增量为key的哈希值(应用另外一种哈希函数),避免了二级聚类
性能比较
设基地址被占用的可能性是 $\alpha$,下表给出了平均检索长度指标
编号 | 冲突解决策略 | 成功检索(删除) | 检索失败(插入) |
---|---|---|---|
1 | 开散列 | $1+\frac{\alpha}{2}$ | $\alpha+e^{-\alpha}$ |
2 | 双散列探查 | $\frac{1}{\alpha}ln\frac{1}{1-\alpha}$ | $\frac{1}{1-\alpha}$ |
3 | 线性探查 | $\frac{1}{2}(1+\frac{1}{1-\alpha})$ | $\frac{1}{2}(1+\frac{1}{(1-\alpha)^2})$ |
实现
Java中的HashMap
已经对哈希表做了很好的实现,使用拉链法(哈希桶)解决哈希冲突,这里有一篇很好的解读
对于使用闭哈希方法的哈希表,在删除元素时,不能够移除该元素,而应该设置一个墓碑标记,表示该元素已经删除。因为探查序列间可能重合,删除某个元素可能影响其他元素的检索(切断其探查序列)
REFERENCE
[1]散列函数. 数据结构与算法[EB/OL].
[2]散列冲突处理 - 北京大学[EB/OL]. Coursera.
文档信息
- 本文作者:wzx
- 本文链接:https://masterwangzx.com/2019/12/11/hashMap/
- 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)