用

H_i

表示处理冲突的第i次探测得到的散列地址，假设得到的另一个散列地址

H_1

仍然发生冲突，只得继续求下一个地址

H_2

，以此类推，直到

H_k

不发生冲突为止，则Hk为关键字的表中的地址。

1.开放定址法

是指可以存放新表项的空闲地址，即向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：

H_i = (H(key)+d_i)\%m

式中，H(key)为散列函数；i = 0,1,2,3...；m表示散列表表长；di为增量序列。取某一增量序列后，对应的处理方法就是确定的。通常有以下4中取法：

1.1 线性探测法

当di=0,1,2....，m-1时，称为线性探测法。

这种方法的特点是：冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查遍全表。

线性探测法可能使第i个散列地址的同义词存入到第i+1个散列地址，这样应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址......从而造成大量元素在相邻的散列地址上“堆积”起来，大大降低了查找效率。

当di = 0^2,1^2，-1^2,2^2，-2^2，...，k^2,-k^2时，称为平方探测法，其中k<= m/2，散列表长度m必须时一个可以表示成 4k+3 的素数，又称二次探测法。

平方探测法时一种处理冲突比较好的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

当

d_i = Hash_2(key)

时，称为再散列法，又称双散列法。

需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量。

它的具体散列函数形式如下：

H_i = (H(key) + i\times Hash_2(key))\%m

初始探测位置H0 = H(key)%m。i是冲突的次数，初始为0。在再散列法中，最多经过m-1次探测就会遍历表中所有位置，回到H0位置。

当di = 伪随机序列时，称为伪随机序列法。

为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。

假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同一次链中进行。

拉链法适用于经常进行插入和删除的情况。

链式法解决冲突时，访问到空指针(NULL)则能判定K不存在，假设再表中插入K，遇到空指针则会生成新节点来cunchuK