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

描述：为产生冲突的地址 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 。

计算：

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

这时存入第四个关键字： 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 ，链地址处理冲突如下图：

三、再哈希法：

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

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