算法小专栏：散列表（二）

本篇将重点介绍：解决散列冲突的四种方案。

一、开放定址法：

1.1 定义：

描述：为产生冲突的地址H(key)求得一个新的地址序列：Hi =（H(key)+ di）% m （i=1，2，3，...，m-1），其中H(key)为哈希函数，m为表长，di称为增量序列。

增量序列通常有以下3种取法：

• 线性探测再散列：di = 1，2，3，...，m-1
• 二次探测再散列：di = 1²，-1²，2²，-2²，3²，-3²，...，k²（k<=m/2）
• 伪随机探测再散列：di = 伪随机数序列

1.2 举例：

例如，在长度为11的哈希表中，已填入关键字 17，29，60的记录，哈希函数为：H(key) = key % 11。

计算：
H(17) = 17 % 11 = 6。故将关键字“17”存在下标为6的位置，位置空着，所以存入未冲突。
H(29) = 29 % 11 = 7。故将关键字“29”存在下标为7的位置，位置空着，所以存入未冲突。
H(60) = 60 % 11 = 5。故将关键字“60”存在下标为5的位置，位置空着，所以存入未冲突。

所以，现在的表的存储状态如下图：

这时存入第四个关键字：38.

计算：H(38) = 38 % 11 = 5。出现冲突，下标为5的位置已存有60。

• 方式一：线性探测再散列。

开始尝试逐次追加di = 1，2，3，...，m-1

得到地址6 => 依然冲突，
得到地址7 => 仍然冲突，
得到地址8 => 不冲突，存入。

最终结果，如下图：

• 方式二：二次探测再散列。

尝试追加 di = 1²，-1²，2²，-2²，3²，-3²，...，k²（k<=m/2）

首先，追加1²，地址6仍然冲突。
再，追加-1²，地址4无冲突，可以存入。

最终结果，如下图：

• 方式三：伪随机探测再散列。

假设伪随机数为9，

H(38) = (38+9)%11 = 3。地址3不冲突，存入。

最终结果，如下图：

二、链地址法：

2.1 定义：

描述：将所有哈希地址相同的记录都链接在同一链表中，以此来解决冲突。

2.2 举例：

已知一组关键字为（19，14，23，01，20，68，84，27，55，11，10，79）。
则按哈希函数H(key) = key % 13，链地址处理冲突如下图：

三、再哈希法：

描述：产生冲突时计算另一个哈希函数（散列函数）的地址，直到冲突不再发生为止。

优点：这种方法不容易产生聚集。
缺点：增加了计算的时间成本。

四、建立公共溢出区：

描述：把冲突的都放在另一个溢出表中，而不会存在基本表里。

这也是解决哈希冲突的一种办法，假设哈希函数的值域为[0，m-1]，那就创建一个[0，m-1]的基本数组，每块内存存放一个记录，另外创建一个溢出数组，一旦发生哈希冲突，就将冲突的值添加至溢出表。