Hash
一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。
Hash算法
1. 除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。
注：对p的选择很重要，一般取素数或m，若p取2的n倍数或者10的n倍数，则H(key)相当于取key的二进制数或十进制数的低n位，若低位相同则容易产生同义词（hash过程中不会考虑k的所有位）
2. 乘法hash法
m:（槽的数量，即hash结构体的长度）， m = 2ʳ（m是以2为底的幂数）
w: 计算机一个字的长度位数（32或64位）
rsh : 右移
A: 一个大于2（w-1），小于2w的奇数（等于计算机字长的奇数），不要取以2为底的幂数
H(key) = (A·k mod 2^w) rsh (w- r)
另一写法：
h(k) = floor(m(kA mod 1))
其中，A： 0<k<1，mod 1表示取出kA的小数部分，floor(x)表示不大于x的最大整数（这里找不到CLRS中那个特殊的记号）。值得注意的是：
kA mod 1 = kA - floor(kA)
在乘法的情况中，对于m的选择与除法时刚好相反，倾向于选择2的幂，同时，会把A表示为s/(2^w)的形式（其中w是计算机的位数）.TAOCP的作者Knuth建议采用A为0.618...也就是我们所知的黄金分割比。通过这样的设定，这个哈希函数的执行得到了一定的简化。如k = 123456， m = 16384（即2^14)，w = 32 时， 可将A表示为特定的形式：2654435769/(2^32).
原理：车轮法，A=s，每次在原来的基础上在圆轮增加k个A，最后得到的槽是随机的
Hash冲突解决
1. 开放寻址法
当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。
开放寻址法的几种探查技术:
- （1）线性探查法(Linear Probing)
https://www.cnblogs.com/zhangbing12304/p/7997980.html - （2）线性补偿探测法
https://www.cnblogs.com/zhangbing12304/p/7997980.html - （3）随机探测
https://www.cnblogs.com/zhangbing12304/p/7997980.html - （4）二次hash
h(k,i)=(h₁(k)+i·h₂(k))MOD m
注：这几种方法都需要限制探查次数n,搜索时最多搜索次数<=n，若找不到则返回nil
2. 链表法
https://www.cnblogs.com/zhangbing12304/p/7997980.html
hash算法的最坏情况
对于不同的hash算法，都存在某一集合key，使得有的元素全部被哈希到同一个桶中，此时数据的存储实际上就是一个链表，那么平均的查找时间为 Θ(n) 。
如何解决：
1. 全域哈希法（Universal Hashing）
全域哈希的基本思想是在执行开始时，从一组哈希函数中，随机地抽取一个作为要使用的哈希函数。就像在快速排序中一样，随机化保证了没有哪一种输入会始终导致最坏情况的发生。同时，随机化也使得即使是对同一个输入，算法在每一次执行时的情况也都不一样。这样就确保了对于任何输入，算法都具有较好的平均运行情况。
https://www.cnblogs.com/soyscut/p/3396216.html
