9.4.3　处理冲突的方法

1.开放定址法

其中，H（key）为哈希函数；m为哈希表表长；di为增量序列。可有下列3种取法：

（1）di＝1，2，3，…，m－1，称线性探测再散列；

（2）di＝12，－12，22，－22，32，－32，…，±k2（k≤m／2），称二次探测再散列；

（3）di为伪随机数序列，称伪随机探测再散列。

例如，在长度为11的哈希表中已填有关键字分别为17，60，29的记录（哈希函数H（key）＝key MOD mMOD 11），现有第四个记录，其关键字为38，由哈希函数得到哈希地址为5，产生冲突。若用线性探测再散列的方法处理时，得到下一个地址6，仍冲突；再求下一个地址7，仍冲突；直到啥希地址为8的位置为“空”时止，处理冲突的过程结束，记录填入哈希表中序号为8的位置。若用二次探测再散列，则应该填入序号为4的位置。

2.再哈希法

RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。

3.链地址法

将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间［0，m－1］上，则设立一个指针型向量

其每个分量的初始状态都是空指针。哈希地址为i的记录都插入到头指针为ChainHash［i］的链表中。在链表中的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。

例9－1 已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则哈希函数H（key）＝key MOD 13和链地址法处理冲突构造所得的哈希表如图9－9所示。

图9－9 链地址法处理冲突时的哈希表

4.建立一个公共溢出区

这也是处理冲突的一种方法。假设哈希函数的值域为［0，m－1］，则设向量Hash－Table［0…m－1］为基本表，每个分量存放一个记录，另设立向量OverTabje［0…v］为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。