hashmap 的一些问题

问题来源自邓俊辉《数据结构》的 ppt

lazy-deletion

在线性试探型的 hashmap 中，其采用了一个 bitmap 来记录被删去的元素

这并非真的是因为删除元素的开销大，而是因为若真的删除，会导致连续区间断开，可能查找失败

素数平方取值

1. $\{0,1,2,3,...{\}}^2\mathrm{mod}M$，$M$ 非素数，此时同余类可能少于 $\lceil M/2\rceil$
2. $\{0,1,2,3,...{\}}^2\mathrm{mod}P$，$M$ 是素数，此时同余类等于 $\lceil P/2\rceil$

首先，全体整数平方的模 $P$ 同余类，等价于 $\{0,1,2,...,P-1{\}}^2$ 的模 $P$ 同余类，这是显然的

然后，当 $P$ 是素数时，$(P-n{)}^2=P^2-2Pn+n^2$ 与 $n^2$ 模 $P$ 同余，因而同余类至多有 $\lceil P/2\rceil$ 种

取 $a,b\in \{0,1,2,...,\lceil P/2\rceil -1\}$ 且 $a>b$

若 $a^2\equiv b^2\mathrm{mod}P$，则 $P|(a^2-b^2)=(a-b)(a+b)$，矛盾

两个方向取值

$\{0,-1,1,-4,4,9,-9,...,-\lfloor P/2{\rfloor }^2,\lfloor P/2{\rfloor }^2\}$ 模 $P$ 构成完全剩余系，当且仅当 $P\equiv 3\mathrm{mod}4$

证明：

取 $a<b$，只需证明 $p|b^2+a^2$ 不成立

反证

模 $p$ 取逆，有 $p|(b/a{)}^2+1$，记 $A=b/a$，则

$$p|A^4-1$$

即 $A^4\equiv 1\mathrm{mod}p$

于是由费马小定理 $A^{p-1}\equiv 1\mathrm{mod}p$，知 $4|p-1$，即 $p\equiv 1\mathrm{mod}4$，与 $p\equiv 3\mathrm{mod}4$ 矛盾

ppt 的证明

它没完全证明，不知道为什么

给的引理是

1. 奇素数 $p$ 可以写为平方和当且仅当 $p\equiv 3\mathrm{mod}4$
2. $n$ 可表示为整数平方和，当且仅当其每一个模 $4$ 余 $3$ 的素因子都是偶数次方

ppt 上的第二条没完全证明，缺少一个引理：

若 $a,b$ 互素，则 $a^2+b^2$ 只有模 $4$ 余 $1$ 的素因子

设 $n=a^2+b^2$，且 $p|n$，$p\equiv 3\mathrm{mod}4$，则设 $gcd(a,b)=q$，有

$$n=a^2+b^2=q^2(c^2+d^2)$$

其中 $c,d$ 互素，于是 $p$ 必不为 $c^2+d^2$ 的因子，于是必为 $q^2$ 的因子，于是 $p^2$ 必为 $q^2$ 的因子