哈希算法：冲突解决与高效查找
一、哈希概念
又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字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.51除法散列法/除留余数法
假设N==100，[0，9999]，哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标
h(key)=key/M
避免M是2或10的幂，key会重复很多，建议M取不太接近2的整数次幂的一个质数
eg.key =123456
int hashi = key%2^16
int hashi = key&(1<<16-1) key只取后16位
int n =16;
int hashi = key&(1<<n-1)
用key’=key>>16，将key和key‘异或结果作为哈希值，尽量让key所有的位都参与计算
1.6处理哈希冲突
1.61开放定址法（比较搓）
在开放地址法中所有的元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储。
有三种规则：线性探测，二次探测，双重探测
eg{19，30，5，36，13，20，21，12}映射到M=11的表中
a、线性探测，但会出现堆积
看似只有19和30的hash0位置冲突，但其实20和21也在抢位置
hc = (key.i)=hashi = (hashi0+i)/M i={1,2,3,...,M-1} 最多探测M-1次
注意给每一个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找
{EXIST,EMPTY,DELETE}
从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置
b、二次探测
依次左右按二次方跳跃探测
h(key)= hash0=key%M
hc(key,i) = hashi=(hash0+-i^2)%M,i={1,2,3,...M/2}
当hashi=(hash0-i^2)%M时,当hashi<0时，需要hashi+=M
eg.将{19，30，52，63，11，22}映射到M=11表中
h(19)=8 h(30)=8 h(52)=8 h(63)=8 h(11)=0 h(22)=0
c、双重散列(了解即可，不实用)
第一个哈希函数计算出的值发生冲突，使用第二个哈希函数，计算出一个跟key相关的偏移值，不断往后探测
h1(key)=hasg09=key%M
hc(key,i)=hashi=(hash0+i*h2(key))%M i={1,2,3,...,M}
1.5.2乘法散列法（对哈希表大小M没有要求）
用关键字乘上常数A（0<A<1），并抽取出k*A的小数部分，后再用M乘以k*A的小数部分，再向下取整。
1.5.3全域散列法
如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如让所有关键字全部落入同一位置中
方法：见招拆招，给散列函数增加随机性，攻击者无法找到确定可以导致最坏情况的数据，即全域散列
ha(key)=((a*key+b)%p)%M
p需要选一个足够大的质数，a选[1,p-1],b选[0,p-1]
需要注意每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后读增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个函数，就会导致找不到插入的key了
1.6.3 链地址法
开放地址法负载因子必须小于1，链地址法的负载因子就没有限制了，可以大于1，但为了哈希冲突概率低，空间利用率，大部分还是控制在1，大于1就扩容
二、代码实现
A、标准
1、插入
但是上面这种扩容有些太复杂了，可改用如下代码
能交换必须优先考虑，赋值麻烦还会涉及深拷贝
2、查找
3、删除
B、链式
1、插入
2、查找
3、删除
