如何用二次探测法处理散列冲突

本篇文章介绍如何利用二次探测法处理散列冲突。散列是一种将节点按关键字的散列地址存储在散列表中的过程。我们在散列的过程中，会发生将不同的关键字映射到同一个散列地址的现象，那么这个时候我们可以使用二次探测法来处理冲突。

工具/原料

纸，笔

智慧的大脑

方法/步骤

我们先来了解一下，二次探测法的增量序列。如下图所示。

若当前扫描的元素的地址已经有元素了，那么，当前元素就保存在该地址的后移偏量。如下图所示。

现在我们来看这样一个序列。如下图所示。

接下来我们将所有元素对11取余。如下图所示。

我们现在来创建一个散列表，如下图所示。

现在根据取余的值将元素放入散列表。如下图所示。

其中47,7,11,16,92这些元素是根据取余的值直接放入散列表的。而29取余的值为7,7的位置上已经有元素了，那么我们放在7+1^2的位置上。3取余的值是3,3的位置上也已经有元素了，那么我们看3+1^2上也有元素，再看3-1^2的位置上没有元素，那么我们现在就放在这里。那么其他元素也是一样的道理。