《因为它们长得不一样——a·k+b 哈希唯一性的优雅证明》
问题简述
设 \(k\) 是一个固定的正整数。对于任意整数 \(a\) 和满足 \(0 \le b < k\) 的整数 \(b\)，定义映射
\[f(a,b) = a \cdot k + b,\]证明 \(f\) 是单射（即不同的有序对 \((a,b)\) 对应不同的函数值）。
反证法（标准做法）
这是最经典的证明思路。
假设存在两对不同的 \((a_1, b_1)\) 和 \((a_2, b_2)\) 满足：
\[a_1 k + b_1 = a_2 k + b_2, \quad 0 \le b_1, b_2 < k.\]移项得：
\[(a_1 - a_2) k = b_2 - b_1.\]考虑右边 \(b_2 - b_1\) 的绝对值：由于 \(0 \le b_1, b_2 < k\)，必有
\[|b_2 - b_1| < k.\]| 左边 \((a_1 - a_2)k\) 要么为 \(0\)，要么绝对值至少为 \(k\)（因为 \(a_1 - a_2\) 是非零整数时，$$ | (a_1 - a_2)k | \ge k$$）。 |
因此等式两边必须同时为 \(0\)，即 \(a_1 - a_2 = 0\) 且 \(b_2 - b_1 = 0\)。故 \(a_1 = a_2,\; b_1 = b_2\)，与假设矛盾。得证。
结论：在条件 \(0 \le b < k\) 下（即 \(k\) 严格大于 \(b\) 的上界），映射 \((a,b) \mapsto a \cdot k + b\) 是单射。换言之，\(f\) 将不同的有序对 \((a,b)\) 映射到不同的整数值。
另一种思路：几何法
说实话，我第一次看到这个问题时，并没有想到反证法，而是想到了另一种做法——几何法。这受到了康托尔配对函数（Cantor pairing function） 的启发。
康托尔配对函数是一种将自然数对 \((x,y)\) 映射为单个自然数的方法，它通过将平面上的点按某种顺序”走遍”来构造。我们不妨也这样想：
把 \((a,b)\) 看成是一个矩形网格中的位置——\(a\) 是行号，\(b\) 是列号，而 \(k\) 是每一行的列数，且 \(0 \le b < k\) 保证了 \(b\) 始终落在有效的列范围内。
在这样一个网格中，将 \((a,b)\) 映射为”从第 0 行第 0 列开始，按行优先数到的序号”：
\[\text{index} = a \cdot k + b.\]现在来证明这个映射是单射。假设 \((a_1, b_1)\) 和 \((a_2, b_2)\) 映射到同一个序号 \(N\)，即
\[a_1 k + b_1 = N = a_2 k + b_2, \quad 0 \le b_1, b_2 < k.\]将 \(N\) 除以 \(k\)，由带余除法（Euclidean division） 的定理：对于任意整数 \(N\) 和正整数 \(k\)，存在唯一的整数商 \(q\) 和余数 \(r\)，满足
\[N = q \cdot k + r, \quad 0 \le r < k.\]由于 \(a_1 k + b_1\) 和 \(a_2 k + b_2\) 都满足这个形式，且 \(0 \le b_1, b_2 < k\)，由商和余数的唯一性即得 \(a_1 = a_2\) 且 \(b_1 = b_2\)。故映射为单射。
注：这个论证本质上与反证法相同，但几何视角让”行号/列号”与”商/余数”之间的对应关系变得更加直观。
此外还需要注意一个细节：若 \(k = b_{\max}\)，则 \(b = b_{\max}\) 时已不满足 \(0 \le b < k\) 的条件，此时映射不再是单射。例如 \((0, k)\) 和 \((1, 0)\) 就冲突：
\[0 \cdot k + k = k, \quad 1 \cdot k + 0 = k.\]这与网格中”每一行只有 \(k\) 列（编号 \(0\) 到 \(k-1\)）”的直观一致——\(k\) 已经是越界的列号了。
再深究一步：从几何到进制
当我们用几何法思考时，你是否注意到一个现象：\(b\) 必须有一个最大值 \(b_{\max}\)。遍历到一行的末尾时，再往后就会”进位”到下一行。
这像什么？像进制数。
在十进制中，个位满了 10 就向十位进 1。类似地，在这里，\(b\) 满了 \(k\) 就向 \(a\) 进 1。
如果我们把 \((a,b)\) 看成一个 k 进制数，其中 \(a\) 是高位，\(b\) 是低位，那么：
\[a \cdot k + b\]就是它在十进制下的值。
于是，我们有了第三种视角——进制视角。下面给出 k 进制表示唯一性的一般证明。
进制表示唯一性的证明
定理：设 \(k \ge 2\) 为正整数。任意非负整数 \(N\) 可以唯一地表示为
\[N = a_m k^m + a_{m-1} k^{m-1} + \cdots + a_1 k + a_0,\]其中 \(m \ge 0\)，\(0 \le a_i < k\) 且 \(a_m \neq 0\)（当 \(N = 0\) 时，取 \(m = 0\)、\(a_0 = 0\)）。
证明（存在性）：反复使用带余除法。 令 \(N_0 = N\)。对 \(i = 0, 1, 2, \dots\) 依次执行
\[N_i = q_i \cdot k + r_i, \quad 0 \le r_i < k,\]并设 \(a_i = r_i\)、\(N_{i+1} = q_i\)。由于 \(N_{i+1} < N_i\)（当 \(N_i > 0\) 时），这个过程必在有限步后终止于 \(N_{m+1} = 0\)。此时
\[N = a_m k^m + a_{m-1} k^{m-1} + \cdots + a_0.\]证明（唯一性）：假设有两种表示
\[N = \sum_{i=0}^m a_i k^i = \sum_{i=0}^n b_i k^i,\]其中 \(0 \le a_i, b_i < k\)。不妨设 \(m \le n\)，并对不足的高位补零（即 \(i > m\) 时视 \(a_i = 0\)）。
考虑模 \(k\) 的同余式：
\[\sum_{i=0}^n a_i k^i \equiv \sum_{i=0}^n b_i k^i \pmod{k}.\]由于 \(k^i \equiv 0 \pmod{k}\) 对 \(i \ge 1\) 成立，上式化为 \(a_0 \equiv b_0 \pmod{k}\)。而 \(0 \le a_0, b_0 < k\)，故 \(a_0 = b_0\)。
两边同时减去 \(a_0 = b_0\) 后除以 \(k\)：
\[\sum_{i=0}^{n-1} a_{i+1} k^{i} = \sum_{i=0}^{n-1} b_{i+1} k^{i}.\]再次模 \(k\) 得 \(a_1 = b_1\)。以此类推，逐位可得 \(a_i = b_i\) 对 \(i = 0, 1, \dots, n\) 均成立。故表示唯一。∎
回到原问题：当我们将 \((a,b)\) 视为一个两位的 k 进制数时，上面的唯一性定理直接保证了映射 \(f(a,b) = a \cdot k + b\) 是单射。这正是进制视角的核心力量——它不仅解释了 \(a \cdot k + b\) 为什么是单射，还揭示了其本质：哈希值的运算（乘 k 再加 b）恰恰就是在做进制数的拼装。
进制数法（多项式视角）
将 \((a,b)\) 看作一个 k 进制数的两位数字（\(a\) 为高位，\(b\) 为低位），那么
\[a \cdot k + b\]就是它在十进制下的数值。这里的核心是进制表示的唯一性：在 k 进制中，每一位数字的取值范围是 \(0\) 到 \(k-1\)，不同的数码组合必然对应不同的数值。
换一个视角：表达式 \(a \cdot k + b\) 在形式上与一次多项式 \(p(x) = a x + b\) 相同。但需要特别注意的是，这里 \(k\) 是一个确定的数值而非未定的变元，因此不能直接套用”多项式恒等定理”（该定理要求等式对所有变元取值成立，而不仅在 \(x = k\) 这一个点成立）。然而，如果限制系数的取值范围，则数值等式可以推出系数相等——这正是反证法所证明的结论。换言之：
若 \(0 \le b_1, b_2 < k\) 且 \(a_1 k + b_1 = a_2 k + b_2\)，则 \(a_1 = a_2\) 且 \(b_1 = b_2\)。
这个结论并不依赖于多项式理论，而是依赖于 \(b\) 的取值范围约束。将表达式类比为多项式，只是为了帮助我们直观理解”系数唯一性”——但这需要以反证法或带余除法作为严格的逻辑基础。
| 与反证法的联系：在反证法的推导中，$$ | (a_1-a_2)k | < k \Rightarrow a_1 = a_2\(这一步骤的实质是：k 进制表示中，高位不同会导致数值差距至少为\)k$$，而低位差不足以弥补这一差距。 |
扩展：更高维的情况
以上思路可以自然推广到更多参数。考虑三元组 \((a,b,c)\)，其中 \(0 \le b < k,\; 0 \le c < k\)，映射为
\[g(a,b,c) = a \cdot k^2 + b \cdot k + c.\]这可以看作是一个 k 进制三位数。下面用反证法证明其单射性。
假设存在两个不同的三元组 \((a_1,b_1,c_1)\) 和 \((a_2,b_2,c_2)\)（均满足 \(0 \le b_i, c_i < k\)）使得
\[a_1 k^2 + b_1 k + c_1 = a_2 k^2 + b_2 k + c_2.\]移项得
\[(a_1 - a_2)k^2 + (b_1 - b_2)k = c_2 - c_1.\]整理为
\[\big((a_1 - a_2)k + (b_1 - b_2)\big)k = c_2 - c_1.\]| 由于 \(0 \le c_1, c_2 < k\)，有 $$ | c_2 - c_1 | < k\(。而左边括号内是整数，记\)m = (a_1 - a_2)k + (b_1 - b_2)\(，则等式为\)m k = c_2 - c_1\(。因此\) | m | k < k\(，故\) | m | < 1\(，即\)m = 0$$。 |
于是 \(c_2 - c_1 = 0\)，且
\[(a_1 - a_2)k + (b_1 - b_2) = 0.\]这就回到了我们已经解决的二元情形。由反证法结论得 \(a_1 = a_2\) 且 \(b_1 = b_2\)。结合 \(c_1 = c_2\)，故 \((a_1,b_1,c_1) = (a_2,b_2,c_2)\)，与假设矛盾。得证。
更一般地，对于 \(n\) 元组 \((a_1, a_2, \dots, a_n)\)（满足 \(0 \le a_i < k\)，其中 \(i \ge 2\)，而 \(a_1\) 可为任意整数），映射
\[h(a_1, a_2, \dots, a_n) = a_1 \cdot k^{n-1} + a_2 \cdot k^{n-2} + \cdots + a_n\]是单射。可以用数学归纳法严格证明：当 \(n = 1\) 时结论平凡。假设对 \(n-1\) 元组成立，对 \(n\) 元组的情形，利用等式
\[(a_1 k^{n-1} + \cdots + a_{n-1} k + a_n) = \big((a_1 k^{n-2} + \cdots + a_{n-1})\big) \cdot k + a_n\]将其化归为 \((m, a_n)\) 的二元情形（其中 \(m = a_1 k^{n-2} + \cdots + a_{n-1}\)），再结合归纳假设即可。这从另一个角度印证了 k 进制表示的唯一性。
总结
本文从一个简单的哈希映射问题出发，给出了三种不同视角的证明：
| 方法 | 核心思想 | ||
|---|---|---|---|
| 反证法 | 利用 $$ | b_2-b_1 | < k$$ 迫使系数相等，是最直接的证明 |
| 几何法 | 按行优先排列成矩形，通过带余除法的唯一性论证 | ||
| 进制数法 | 将 \((a,b)\) 视为 k 进制数，利用进制表示的唯一性 |
殊途同归——它们最终都指向同一个结论：只要 \(k\) 严格大于 \(b\) 的上界，\(a \cdot k + b\) 就是 \((a,b)\) 的一个完美哈希。
