哈希算法：冲突解决与高效查找
一、哈希概念
又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字 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 的表中。（图示：线性探测过程）
