哈希算法：冲突解决与高效查找

一、哈希概念

又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字 key 跟存储位置建立一个映射关系，查找时通过这个哈希函数，计算出 key 存储的位置，进行快速查找。

1.1 直接定位法

当关键字的范围比较集中时，简单高效，但局限性太大（而且必须是整形）。

1.2 哈希冲突

假设我们只有数据范围是 [0, 9999) 的 N 个值，我们要映射到一个 M 个空间的数组中（一般情况下 M >= N），那么就要借助哈希函数，关键字 key 被放到数组的 h 位置，注意 h 计算的值必须在 [0, M) 之间。

这里存在一个问题，两个不同的 key 可能会映射到同一个位置，这是无法避免的，所以就要尽可能的设计优秀的哈希函数。

1.3 负载因子

假设哈希表中已经映射存储了 N 个值，哈希表大小是 M，负载因子为 N/M。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越小，空间利用率越低。通常希望负载因子较小。

1.4 将关键字转为整形

我们把关键字映射到数组中位置时，一般是整形好做映射计算。

1.5 哈希函数

一个好的哈希函数应该让 N 个关键字被等概率地均匀散列分布到哈希表的 M 个空间中，但实际却很难做到，所以需要认真设计。

1.5.1 除法散列法 / 除留余数法

假设 N == 100，[0, 9999]，哈希表的大小为 M，那么通过 key 除以 M 的余数作为映射位置的下标。

h(key) = key % M

避免 M 是 2 或 10 的幂，key 会重复很多，建议 M 取不太接近 2 的整数次幂的一个质数。例如 key = 123456：

int hashi = key % (1 << 16); // 不推荐
int hashi = key & ((1 << 16) - 1); // 只取后 16 位

更好的做法是用 key' = key >> 16，将 key 和 key' 异或结果作为哈希值，尽量让 key 所有的位都参与计算。

1.5.2 乘法散列法

对哈希表大小 M 没有要求。用关键字乘上常数 A（0 < A < 1），并抽出 kA 的小数部分，后再用 M 乘以 kA 的小数部分，再向下取整。

1.5.3 全域散列法

如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如让所有关键字全部落入同一位置中。方法：见招拆招，给散列函数增加随机性，攻击者无法找到确定可以导致最坏情况的数据，即全域散列。

ha(key) = ((a * key + b) % p) % M

p 需要选一个足够大的质数，a 选 [1, p-1], b 选 [0, p-1]。需要注意每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个函数，就会导致找不到插入的 key 了。

二、处理哈希冲突

2.1 开放定址法

在开放地址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储。有三种规则：线性探测，二次探测，双重探测。

例如 {19, 30, 5, 36, 13, 20, 21, 12} 映射到 M=11 的表中。（图示：线性探测过程）

2.1.1 线性探测

从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。

hc(i) = (hashi0 + i) % M, i = {1, 2, ..., M-1}

最多探测 M-1 次。注意给每一个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。状态包括：{EXIST, EMPTY, DELETE}。看似只有 19 和 30 的 hash0 位置冲突，但其实 20 和 21 也在抢位置（堆积现象）。

2.1.2 二次探测

依次左右按二次方跳跃探测。

h(key) = hash0 = key % M
hc(key, i) = (hash0 + (-1)^i * i^2) % M  // 简化描述，通常为 +/- i^2

当 hashi = (hash0 - i^2) % M 时，当 hashi < 0 时，需要 hashi += M。例如将 {19, 30, 52, 63, 11, 22} 映射到 M=11 表中。（图示：二次探测过程）

2.1.3 双重散列

第一个哈希函数计算出的值发生冲突，使用第二个哈希函数，计算出一个跟 key 相关的偏移值，不断往后探测。

h1(key) = hash0 = key % M
hc(key, i) = (hash0 + i * h2(key)) % M, i = {1, 2, ..., M}

2.2 链地址法

开放地址法负载因子必须小于 1，链地址法的负载因子就没有限制了，可以大于 1，但为了哈希冲突概率低，空间利用率，大部分还是控制在 1，大于 1 就扩容。（图示：链地址法结构）

哈希算法：冲突解决与高效查找