平方试探Quadratic probing

以平方数为距离，确定下一试探桶单元

[hash(key) + 1^2] % M，[hash(key) + 2^2] % M，[hash(key) + 3^2] % M，......

优点、缺点及疑惑

数据聚集现象有所缓解

查找链上，各桶间距线性递增

一旦冲突，可聪明地跳离是非之地

若涉及外存，I/O将激增

只要有空桶，就一定能找出来吗？不能

【装填因子须足够小】

M若为合数，n^2 % M可能的取值必然少于M/2（向下取整）种——此时，只要对应的桶均非空

M若为素数：n^2 % M可能的取值恰好会有M/2（向下取整）种——此时，恰由查找链的前M/2（向下取整）项取遍

定理：若M是素数，且装填因子λ<=0.5，就一定能够找出，否则，不见得

【查找链前缀须足够长】

反证：假设M是素数，且装填因子λ<=0.5，存在0<=a<b<M/2（向下取整），使得沿着查找链，第a项和第b项彼此冲突

于是：a^2和b^2自然属于M的某一同余类，亦即

a^2=b^2 （mod M)

b^2 - a^2 = (b+a)(b-a) = 0 (mod M)

然而：0<b-a<a+b<M ——与M为素数矛盾

双向平方试探

自冲突位置起，依次向后试探

[hash(key) + 1^2] % M，[hash(key) - 1^2] % M，[hash(key) + 2^2] % M，[hash(key) - 2^2] % M，[hash(key) + 3^2] % M，[hash(key) - 3^2] % M，......

正向和逆向的子查找链，各包含M/2（向下取整）个互异的桶

表长取作素数M=4*k+3，必然可以保证查找链的前M项均互异

反之，M=4*k+1，就必然不可使用

双平方定理Two-Square Theorem of Fermat

任一素数p可表示为一对整数的平方和，当且仅当p%4 =1

只要注意到：

(u^2+v^2)*(s^2+t^2) = (us+vt)^2 + (ut - vs)^2

就不难推知：

任一自然数n可表示为一对整数的平方和，当且仅当在其素分解中，形如M=4*k+3的每一素因子均为偶数次方