之前简单介绍了线性探测，平方探测，双散列这3种方法，然后又举了线性探测的2个例子，下面我们来讲讲第二种开放地址法，叫做平方探测法，或者叫做二次探测，为什么叫平方探测？因为它采用的增量序列是 ,前面线性探测呢，是+i,就是在原来算出来的哈希地址上，加一个偏移量，这个偏移量是我们探测次数的一个线性函数，那么在平方探测法里面，它是一个平方函数，所以 ,我们举一个例子，还是那么9个数，哈希表长呢，现在把它设为11，散列函数也把它设为给11求余，对这样的9个数，它所对应的散列函数值，跟线性探测的时候一样，因为都是对11求余，

接下来我们看一下，插入散列表的过程，到底是怎么样的，我们先来一个元素47，那么47它的散列地址值呢，是等于3，所以就放在这个位置，

而7放这个位置，

接下来来了一个29，29的散列值等于7，那么好，又冲突了，有冲突的时候我们做探测，第一次探测是原来基础上 ,那么就挪到8这个位置了，所以29就放在这里，

接下来11，11的话，它的散列地址等于0，然后这个地方没有冲突，

再接下来9，9呢它的散列地址等于9，也没有冲突，

放在这个位置了，再下来，84，那么84呢，它的散列值是等于7，那么要放这个位置（横轴：插入84，竖轴: 7)，这个位置发现有冲突，有冲突就试探下一个位置，那就是 ,这个位置是29，已经放进去了，还有冲突，这个时候我们做再下一次的探测，是 , 就到了6号位置，就放这

这个位置，是空位，就放上去了，再下来，54，54的散列值等于10，10这个位置原来是空位，就放上去了，

再下来是20，20我们的散列值是等于9，9这个位置是有元素值的，所以有冲突，有冲突就 , 这个54，还是有冲突，那么所以接下来这个位置 , 为29，还有冲突，那么这个时候就是 ,从9这个位置 ， 就是加4了，往右数，到54后，跳到11，然后是一个空格，再到20(黄色标记部分)

这个位置是空的，那么就把20放上去了，30它的值是8(即横轴为插入30，竖轴为8)，所以在8这个位置，有冲突， , 还有冲突， , 还有冲突，那么回到刚才的地方(即横轴为插入30，竖轴为8), 那么就要 了，2的平方等于4，还是像刚才一样，先往右，到达54之后，到最左边，往右移动两格，插入30，这个地方是空的。

就放上去了。所以这是我们最后这样的一个结果。那么根据我们这样的一个结果，我们很容易算出它的平均成功查找次数，也就是把它冲突的次数加1，求个平均值就是了，它的平均查找次数呢，等于2，这个是指的找在这个表里的，总共9个元素，平均查找的次数是两次，我们知道线性探测，是这个位置有冲突的时候，往后面找，再往后面找，按照这样的一种策略，只要表里面有空，我就一定能找到那个空位，所以只要有空，我一定把这个元素放上去，而二次探测，或是叫平方探测，它是跳着来的，有可能我本来有空位的，但是你就是找不着，跳来跳去，老是找不着这个位置，所以有没有可能有这个问题？就是说我这个散列表里面，是有空间的，但是你这么跳来跳去，老找不到那个位置，我们来看一下，好像是有这种情况，比方说我们这个表呢，

大小等于5，散列函数呢，是对5求余，那么我们已经放了3个元素，5，6，7

5求余等于0，所以5放在第一个位置，6放在下一个，6求余等于1，7求余等于2，接下来我们来一个新的元素，这个元素叫11，11求余的结果是多少，是等于1，也就是11这个元素，计划是放在6这个位置的，

但这个位置已经有元素了，这个位置有冲突，那么就 ,就到了7这个位置，有冲突，

就 , 还有冲突，

那么在6这个位置 , 往右数，2，3，4，0（下面编号），又回到了0这个有冲突的地方。

那么就 ,这时会到7这个位置

还有冲突，一直继续， , ,它的结果就在0，2，0，2跳来跳去，当然后面没有继续算下去，算来算去就是找不着后面的两个空位，所以这是二次探测它和一次探测相比呢，它的一个缺陷，但是它避免了线性探测的一个很大问题，叫聚集，线性探测很容易聚集，二次探测也有聚集现象，但没那么严重，还好我们有结论，如果你这个表大小设计成4k+3的形式，也就是表的大小是7，或者是11，或者是19，就4k+3这种形式，而且是这种形式的素数的时候，那么只要有空位，一定能够找的着。这个是理论上可以证明的。