hashmap 的一些问题

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

lazy-deletion

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

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

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

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

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

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

${0, - 1, 1, - 4, 4, 9, - 9, ..., - ⌊ P /2 ⌋^{2}, ⌊ P /2 ⌋^{2}}$ 模 $P$ 构成完全剩余系，当且仅当 $P \equiv 3 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 mod p$

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

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

给的引理是

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

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

设 $n = a^{2} + b^{2}$ ，且 $p ∣ n$ ， $p \equiv 3 mod 4$ ，则设 $g c d (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}$ 的因子