关于二次探测如何保证探测到表所有项的证明

共有两种形式的二次探测，分别为

 (此证明仅讨论此形式)

一、预备知识

二次剩余

当存在某个  ， 令式子  的   有解时，称   是模   的二次剩余；当   无解时，称   是模   的二次非剩余。

列出一张  的二次剩余列表如下：

d	1	2	3	4	5	6	7	8	9	10	11	12	13	14
d^2	1	4	9	16	25	36	49	64	81	100	121	144	169	196
mod 2	1	0	1	0	1	0	1	0	1	0	1	0	1	0
mod 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1
mod 4	1	0	1	0	1	0	1	0	1	0	1	0	1	0
mod 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1
mod 6	1	4	3	4	1	0	1	4	3	4	1	0	1	4
mod 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0
mod 8	1	4	1	0	1	4	1	0	1	4	1	0	1	4
mod 9	1	4	0	7	7	0	4	1	0	1	4	0	7	7
mod 10	1	4	9	6	5	6	9	4	1	0	1	4	9	6
mod 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9

从表中我们可以看出一些规律。首先，剩余数以   的长度为一个段一个段地轮回，这很好理解，因为取模为  时， 其值必然小于等于  ；其次，在这一段的剩余数中， 左右两边是对称的，如mod 7时的1、4、2与2、4、1是对称的，也就是说，mod 7时的二次剩余只有3个。

费马小定律

设  为素数，   是任意整数，且不为   的倍数，则有   。

先证明一个引理：设  为素数，   是任意整数，且不为   的倍数，则有序列   与序列   不考虑顺序时等价。

假如序列   存在   重复，也即   ，由于   不能被   整除，即只能是   被   整除，又因为   ，所以   ，能被   整除的情况只能是   ，也就是说存在重复只能是两个值就是同一个的情况， 即序列  元素均在   以内，且不重复，即与序列   不考虑顺序时等价。

根据引理，将序列   与序列   元素分别累乘取模   ，两边应该是相等的，也即   

欧拉判别法则

若  是模   的二次剩余，则有   ；若   是模   的二次非剩余，则有   。

因为  是模   的二次剩余，有   ，   不为0，则   不能被   整除，则   不能被   整除。

根据费马小定律，有  。

同样根据费马小定律，   ，   要么为1，要么为-1，而   要么是二次剩余，要么是二次非剩余，因此，当   是模   的二次非剩余时，有   。

二、证明

将以  时进行说明：

假如0位已被哈希占用，此时触发二次探测再散列，先忽略负值的跳位，有   ，这与二次剩余问题同出一撤，那么什么情况下每次探测的空格不重复呢？

假设存在   ，使探测的空格重复，有   ，存在以下条件使此等式不成立（反过来说不成立说明不重复）：

• 要令任意  和任意  ，使 不被  整除，首先  不能是只包含  或  其中的质因子的合数，由于  和  是任意的，也即  不能是合数，  得是质数。
• 由于 和  是任意取值的，且  ，即符合条件  即可，因此有  

因此，当  为质数，并且增量序列为：   时，可以保证探测空格不重复，如上例  时，  对应二次剩余下标  。

那么剩下的  呢？其实这些就是  时的二次非剩余。

若  是  的二次剩余集合，它们必然是各不相同的，现假设有集合  ，由于  之间各不相同，则  必然也各不相同。如此，假若可以令集合  与集合  没有交集，则它们的并集元素有  个，也就是等于所有剩余集合。由于集合  是二次剩余集合，则需找到一个  ，令集合  等于二次非剩余集合即可。

我们根据欧拉判别法则进行命题转换：当  时，令  即可。

对  进行二项展开有：

     

从而得到  ，根据费马小定律，可得  ，要使之恒成立，  必须为奇数，即  为  形式时，有  必为奇数。

因此，当  为  形式的质数时，集合  就是  的非剩余集合，也就是说剩余集合与非剩余集合是关于模  对称的。现想象将哈希列表首尾相连形成一个环，从起始点0向逆时针方向移位代表的是正数增位序列  移位，由于对称，剩下的二次非剩余下标位置，必是顺时针方向的相反意义的二次剩余移位，由于二次剩余和非二次剩余之和为  ，加上0位的一格即为哈希表总长度，因此，最终增量序列  可以扫描到全表。

三、总结

当哈希表长为形如  的质数时，移位增量序列  可以扫描到全表。