哈希表检索的实现

哈希函数

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

除余法

用关键码 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$，下表给出了平均检索长度指标

实现

Java中的HashMap已经对哈希表做了很好的实现，使用拉链法(哈希桶)解决哈希冲突，这里有一篇很好的解读

对于使用闭哈希方法的哈希表，在删除元素时，不能够移除该元素，而应该设置一个墓碑标记，表示该元素已经删除。因为探查序列间可能重合，删除某个元素可能影响其他元素的检索(切断其探查序列)

REFERENCE

[1]散列函数. 数据结构与算法[EB/OL].
[2]散列冲突处理 - 北京大学[EB/OL]. Coursera.