WZX's blog 海滩上捡贝壳的孩子

哈希表检索


哈希表检索的实现

哈希函数

哈希函数是一种从任何一种数据中创建小的数字“指纹”的方法。这样,我们就可以将关键码映射为存储索引,检索时只需计算出给定值的哈希值,就可以像顺序表那样找到对应记录。

除余法

用关键码 x 除以 M (往往取散列表长度,取素数),并取余数作为哈希值

连续的关键码会映射成连续的哈希值,这样保证了连续的关键码不发生冲突,但是会占据连续的数组单元,导致哈希性能的降低

乘余取整法

$hash(key)=\lfloor n\times ((A\times key)\%1) \rfloor$,其中 $\%1$ 表示取小数部分,$0<A<1$ 一般取黄金分割最理想

平方取中法

先通过求关键码的平方来扩大差别,再取其中的几位或其组合作为哈希值

数字分析法

因为哈希函数的目标是尽可能让哈希值在其范围上分布均匀,以减少冲突的发生,所以可以取那些分布均匀的位作为哈希值

设有 $n$ 个 $d$ 位数,每一位可能有 $r$ 种不同的符号,定义第$k$位的均匀度 $\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.


Similar Posts

上一篇 外排序算法

Comments