二次剩余

散列表——平方探测——二次剩余

散列表的平方探测

我们先回顾一下散列表（Hash Table）的平方探测（Quadratic Probing）：

平方探测是一种用于解决哈希冲突的方法。哈希冲突发生在两个或多个不同的键通过哈希函数映射到同一个索引位置时。平方探测通过改变冲突位置的探测方式，来减少冲突并均匀分布键值。计算公式为：探测位置=(初始哈希位置+i^2)%表长

再来看看《数据结构与算法分析——C语言描述（Mark Allen Weiss 第二版机械工业出版社）》119页定理5.1的证明，这是一个有关平方探测的重要结论，这里的证明似乎不是很完整。

定理5.1：如果使用平方探测，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。

定理5.1：一个平方探测的结论

证明的倒数第二行

“因此任何元素都有 $\lfloor TableSize/2\rfloor$ 个可能被放到的位置。”

这句话乍一看并不显然，因为定理先证明了前 $\lfloor TableSize/2\rfloor$ 个备选位置是互异的，但是并没有说明后面的 $\lfloor TableSize/2\rfloor$ 是什么情况。有可能后面可能的情况与前面不同，导致任何元素都有 $TableSize$ 个可能的位置。那按书中的说法，应该在此句的 $\lfloor TableSize/2\rfloor$ 前加“至少”。但是我们下面会证明，书中的说法是对的，即只有 $\lfloor TableSize/2\rfloor$ 种可能的结果。也就是说，后面一半的备选位置和前面一半是相同的。

平方探测是在计算冲突元素在发生第 $i$ 次冲突将被放到的新位置： $F(x,i) = x \%p+i^2$，假设 $p$ 为 $hash table$ 的大小，为奇素数，$hash(x)=x\%p$ ,

那么更确切地，$F(x,i) = (x \%p+i^2)\%p=(x\%p+i^2\%p)\%p$ 这是因为$(a+b)\%p=(a\%p+b\%p)\%p$.

上面 $F(x,i)$的结果在 $x$ 固定的情况下只取决于 $i$，即冲突发生的次数。所以只考虑 $i^2\%p$ 在 $i$ 取遍正整数时所有的可能结果即可。结果不会超过$p$个（因为模 $p$ 的同余类只有$p$种）。

实际上，$i^2\%p$ 在 $i$ 取遍正整数时所有的可能结果就是模 $p$ 的所有二次剩余，结果的个数就是二次剩余的个数加一，下面将会证明模 $p$ 的二次剩余个数为 $\frac{p-1}{2}$。

二次剩余的定义

二次剩余的定义如下：

一个正整数$a$称为模$p$的二次剩余，如果存在某个整数$i$使得$i^2\equiv a \pmod{p}$ 成立，否则称为模$p$的二次非剩余。

我们使用如下记号：勒让德符号（Legendre）来表示二次剩余关系 $$ (\frac{a}{p})= \begin{cases} 1, & a \text{是} p \text{的二次剩余}\ -1, & a \text{是} p \text{的二次非剩余}\ 0, & p|a \end{cases} $$

二次剩余的个数

现在我们来求解模 $p$的二次剩余的个数，即 $i^2\equiv a \pmod{p}$在 $i$ 取遍正整数时，正整数 $a$的个数。

先考虑 $i$ 的取值，显然只要从1取到p即可，若$i>p，$则 $\exists q\in Z, i=qp+r, 0<r<p$ 此时 $i^2\%p=r^2\%p$，仍只需考虑小于p的情况即可。

设 $1\leq x < y \leq p$,且$x^2\%p\equiv y^2\%p$. 故有 $p|(x^2-y^2)$ ，即 $p|(x+y)(x-y)$ 由$x,y$的取值范围可知 $p|(x+y)$，进一步地， $x+y=p$。

于是我们得到了这样的关系：当两个数和为模数的时候，它们的平方模除这个模数结果相同。因此，对于 $(1,p-1),(2,p-2),···$ 这 $\frac{p-1}{2}$ 个数对（别忘了p为奇素数），处于同一数对中的数，它们的平方模除$p$的结果相同，不同数对中的元素模除$p$结果不同，共有 $\frac{p-1}{2}$ 个结果。

因此二次剩余的个数就是 $\frac{p-1}{2}$。

二次剩余的检验

有时候，我们已知 $i^2\equiv a \pmod{p}$ 式中的$a, p$要去求满足条件的 $i$（这就是求解二次剩余方程）。但是这样的$i$并不一定存在（这种情况就称a是模p的二次非剩余）。

当然也有很多情况，我们不知道模除 $p$ 的二次剩余是什么，这时候 $i$ 就更不知道了，不过我们现在已经知道了二次剩余的个数，所以只需从1到 $\frac{p-1}{2}$ 之间一个一个检验就行。那么如何检验一个数它是不是模除p的二次剩余呢？欧拉告诉我们有欧拉准则（Euler Criterion）： $$ (\frac{a}{p})\equiv a^{\frac{p-1}{2}}\pmod{p}= \begin{cases} 1 \pmod{p} & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \ -1 \pmod{p} & \text{如果 } a \text{ 不是模 } p \text{ 的二次剩余} \end{cases} $$

所以回到我们的问题上来，冲突时发生时，利用平方探测 $hashtable$ 中所有备选的位置，就是模 $TableSize$ 的二次剩余 ($i^2\%p$) 加上一个 $x\%p$ 再模除 $p$，但是我们只用考虑个数，它有 $\lfloor TableSize/ 2\rfloor$ 个。于是，再看定理5.1，表至少一半空时，二次剩余至少有两个，所以一定有空的备选位置，故一定可以放下一个新元素。

散列平方探测插入失败问题

最后来看一个判断题，正是这篇文章的缘起。

If 7 elements have been stored in a hash table of size 13 at positions { 0, 1, 2, 4, 5, 10, 11 }, and the hash function is H(x) = x%13. Then an empty spot can't be found when inserting the element 40 with quadratic probing.

答案是✔ 一般的解法是不断用 $(40+i^2) mod{13}(i=0,1,2, \cdots)$ 求得新的插入位置，计算后发现结果是 $1, 2, 5, 10, 4, 0, 11, 11, 0, 4, 10, 5, 2$ 这13个数循环，全是题中已插入的位置，所以40不能成功插入。

现在我们可以利用上面对二次剩余的讨论对这个循环给出解释。先转换一下插入位置表达式： $(40+i^2) mod{13}=(40 mod{13}+i^2 mod{13})mod{13}=(1+i^2 mod{13})mod{13},(i=0,1,2, \cdots)$，这个结果可能的取值个数（也就是可插入位置个数），取决于 $i^2mod{13}的值的个数 $。

首先，可以确定模除13的二次剩余的个数：$\frac{p-1}{2}=\frac{13-1}{2}=6$。在这道题里，模数的结果可以为0，故在散列中有 $6+1=7$ 个可插入位置。接着我们就仅需判断所给的positions是否为这7个可插入位置。（实际上得到的循环已经证实了确实是这7个）

现在可以使用上面的欧拉准则，将所给的position标号减去1后求6次方然后模除13，看看结果是不是1（此时即为模13的二次剩余）或者0。注意：0减去1结果取12，因为 $1+12=13\equiv0 mod{13}$

下面是验证的Python代码：

positions=[0,1,2,4,5,10,11]
res=[0,1]
p=13
for position in positions:
    if position==0:
        position=13
    if (position-1)**((p-1)/2)%13 in res:
        print(f"position {position%13} is not insertable")