几个概念
哈希函数
数据中的关键字映射到存放位置的映射函数叫做 哈希函数 。
哈希冲突
$K_i,K_j(i\neq j)$是两个关键字。 把$K_i \neq K_j$,并且$h(K_i)=h(K_j)$现象叫做哈希冲突，
这样的$K_i,K_j$叫做 同义词
哈希冲突的可能性与三个因素有关：
- 填装因子$\alpha$。设已存入数据个数为n，哈希地址空间大小m，$\alpha=\dfrac{n}{m}$
- 哈希函数。如果选择得当，可以使哈希地址尽可能均匀分布在地址空间上。
- 哈希冲突函数：为解决
哈希冲突问题，有哈希冲突函数，哈希冲突函数的选取也影响哈希冲突的可能性
几个经典哈希函数
余数法
关键字K，哈希表长度为m，那么：
$h(K)=K \mod m$
优点：
算法简单，适用范围广
如果关键字均匀，那么映射到每个地址的概率也均匀，减少了哈希冲突的概率
直接定址法
关键字K加上某个常量C
$h(K)=K+C$
优点：
计算简单
不可能有哈希冲突
缺点： 如果有1~1000的7个数字需要存放，可能需要1000个内存单元，造成大量浪费
数值分析法
分析数据内容，找出比较均匀的位（可以是多个），组合成为哈希地址
例如，某组数据有1000个数字，这些数字第1,3,6位取值比较均匀，那么可以提取1,3,6位，组成一个三位数作为哈希地址
哈希冲突的解决方法
开放定址法
非同义关键字 ： 开放定址法中，为了把某个发生哈希冲突的数据放到另一个空闲单元d中，因为对应的关键字的哈希值不为d，所以称为非同义关键字
开放定址法中，哈希空闲单元既向同义关键字开放，又向非同义关键字开放，至于填入哪个，要看谁先占用它
非同义词冲突 在解决哈希冲突时，如果$K_i \neq K_j(i\neq j), h(K_i) \neq h(K_j)$, 但哈希冲突函数$h_1(K_i) = h(K_j)$，这种现象叫做非同义词冲突
开放定址法有以下几种：
1.线性探查法
d位置发生哈希冲突时，依次探查d的下一个地址。如果探查到哈希表尾部(m-1)时，下一个探查0位置.
\[\left \{ \begin{array}{lcl} d_0=h(K)\\ d_i=(d_{i-1}+1)\mod m \end{array}\right.\]缺点是容易产生堆积问题，如果连续出现几个同义词后，将连续占用哈希表的内存单元
2.平方探查法
\[\left \{ \begin{array}{lcl} d_0=h(K)\\ d_i=(d_{i-1}+2^{i-1})\mod m \end{array}\right.\]3.伪随机数法
\[\left \{ \begin{array}{lcl} d_0=h(K)\\ d_i=(d_{i-1}+R)\mod m \end{array}\right.\]其中，R是一个伪随机数
链表法
如果没有发生哈希冲突，直接存放该数据。
如果发生了哈希冲突，把冲突的数据放到链表中
