几个概念
- 哈希函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为H(K)。
- 冲突：对不同的关键字可能得到同一哈希地址的现象，即key1 != key2,而H(key1)=H(key2)。
- 同义词：发生冲突的不同关键字。
- 哈希表：根据关键字直接进行访问的数据结构，建立了关键字与存储地址之间的一种直接映射关系。
哈希函数的构造方法
（1）直接定址法
取关键字或关键字的线性函数值为哈希地址，即H(key)=key或H(key)=a*key+b。
这种方法对于不同的关键字不会发生冲突，但关键字分布不连续，空位多，会造成存储空间的浪费。
（2）除留余数法
取关键字被某个不大于哈希表表长length的数p除后所得的余数为哈希地址，即H(key)=key % p，p<=length。
p一般取一个不大于length但最接近或等于length的质数。
（3）平方取中法
取关键字平方后的中间几位为哈希地址。
（4）数字分析法
设关键字是r进制数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干位组成哈希地址。
（5）折叠法
将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为哈希地址。
当关键字位数很多，而且关键字中每一位上数字分布大致均匀是适用。
处理冲突的方法
- 开放定址法
H~i~ = (H(key) + d~i~) % length，i = 1,2,3,...,length。
其中：H(key)为哈希函数；length为哈希表表长；d~i~为增量序列。
对于d~i~有几种不同的取法：
（1）d~i~ = 1,2,3,...,length-1，称为线性探测再散列；
（2）d~i~ = 1^2^,-1^2^,2^2^,-2^2^,3^2^,...,+-k^2^(k<=length/2)，称为二次探测再散列；
（3）d~i~ = 伪随机数序列，称为伪随机探测再散列。
- 再哈希法
H~i~ = RH~i~(key)，i = 1,2,3,...,length。
RH~i~均为不同的哈希函数，即在同义词产生冲突时计算另一个哈希函数地址，直到冲突不在发生。
- 链地址法
将所有关键字为同义词的记录存储在同一线性表中。
