哈希通过某种规则把原数据映射为较短的摘要。由于值域通常小于原数据空间，哈希一般不是单射：不同对象可能得到相同的哈希值，这种情况称为哈希冲突。

因此，哈希值不同可以推出原对象不同；哈希值相同通常只能作为原对象相同的必要条件，还需要接受一定的误判概率，或在哈希相同时继续比较原对象。

哈希表：

开放寻址和拉链法只能处理多个键落到同一桶的情况，并不能消除哈希冲突。哈希函数分布较均匀且负载因子受到控制时，插入、删除、查询的期望复杂度为 $O(1)$；最坏情况下仍可能退化到 $O(n)$。

开放寻址法：

开放寻址法使用定长数组直接保存键值对。

取一个表长 $M$，假设插入的数是 $x$，初始位置为 $f(x)modM$。若该位置已经有元素，则依次检查下一个位置，直到找到可用位置。探测次数至多为 $M$；若整张表都没有可用位置，插入必须报告失败，不能继续循环。

删除元素时，不能直接把位置标为空，否则会截断其它键的探测链。通常使用“墓碑”标记：查询越过墓碑继续探测，插入则可以复用遇到的第一个墓碑。负载因子过高或墓碑过多时，应扩容并重新散列。

拉链法：

拉链法为每个桶维护一个链表、动态数组或其它容器。

取一个模数 $M$，假设插入的数是 $x$，则 $f(x)=xmodM$，将 $x$ 插入 $f(x)$ 位置所在的数据结构。

---

事实上，开放寻址法和拉链法可通过修改哈希函数，改善键的分布。

开放寻址法还可以修改步长。拉链法也可修改位置上的数据结构。

基于开放寻址法的哈希表实现：

点击展开代码

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct Hash_Map {
    enum State : unsigned char { EMPTY, OCCUPIED, DELETED };
    State state[N]{};
    u64 a[N];
    int b[N];
    stack<int> q;
    void clear() {
        while (q.size()) {
            auto now = q.top();
            q.pop();
            state[now] = EMPTY;
        }
    }
    const u64 s1 = rnd(), s2 = rnd() | 1, s3 = rnd() | 1;
    u64 f(u64 x) {
        x += s1;
        x = (x ^ (x >> 33)) * s2;
        x = (x ^ (x >> 30)) * s3;
        return x;
    }
    bool find(u64 x) {
        int now = f(x) % N;
        for (int cnt = 0; cnt < N; cnt++) {
            if (state[now] == EMPTY)
                return false;
            if (state[now] == OCCUPIED && a[now] == x)
                return true;
            now = (now + 1) % N;
        }
        return false;
    }
    int get(u64 x) {
        int now = f(x) % N;
        int del = -1;
        for (int cnt = 0; cnt < N; cnt++) {
            if (state[now] == OCCUPIED && a[now] == x)
                return now;
            if (state[now] == DELETED && del == -1)
                del = now;
            if (state[now] == EMPTY) {
                if (del != -1) {
                    now = del;
                } else {
                    q.push(now);
                }
                state[now] = OCCUPIED, a[now] = x, b[now] = 0;
                return now;
            }
            now = (now + 1) % N;
        }
        if (del != -1) {
            state[del] = OCCUPIED, a[del] = x, b[del] = 0;
            return del;
        }
        return -1;
    }
    bool erase(u64 x) {
        int now = f(x) % N;
        for (int cnt = 0; cnt < N; cnt++) {
            if (state[now] == EMPTY)
                return false;
            if (state[now] == OCCUPIED && a[now] == x) {
                state[now] = DELETED;
                return true;
            }
            now = (now + 1) % N;
        }
        return false;
    }
    int &operator[](const u64 x) {
        int now = get(x);
        if (now == -1)
            throw overflow_error("Hash_Map is full");
        return b[now];
    }
};

其中，state 的初值均为 EMPTY，键数组使用 u64，不会截断传入的键。新键对应的值会初始化为 $0$。两个随机乘数强制取奇数，使乘法在模 $2^{64}$ 意义下是一个排列，不会仅因乘数为偶数而系统性丢失部分桶。get 最多探测 $N$ 个位置，表满且没有墓碑可复用时返回 -1；operator[] 在这种情况下显式报错。模板不自动扩容，使用时应让 $N$ 明显大于同时保存的键数，并在墓碑过多时重建哈希表。

多项式模数哈希：

$$h(a)=\sum _{i=1}^n{a}_i\cdot bas{e}^{i-1}modp$$

优点：

• 可以将字符串映射到 $[0,p)$ 中，方便存储。
• 模运算具有优秀的性质，可以支持很多其它操作（比如修改字符串中的某一个字符，只需要加减取模即可）。

缺点：

• 映射范围较小容易产生哈希冲突。

自然溢出：

使用 unsigned long long 进行运算，不使用取模，任凭数据在底层自动“溢出” $64$ 位，仅保留低 $64$ 位的结果。

优点：

• 运算速度快。

缺点：

• 本质是对 $2^{64}$ 取模，模数过于特殊，十分容易卡。

值域与哈希冲突

若哈希函数把较大的输入域映射到 $M$ 个值中，则由鸽巢原理可知冲突必然存在。冲突多少取决于哈希函数在输入集合上的实际分布，不能由一个没有对应映射关系的 $gcd$ 直接推出。

最大公约数只在某些特定映射中能给出精确结论。例如对完整剩余系 ${\mathbb{Z}}_M$ 上的仿射映射

$$h(x)=(Ax+B)modM,$$

有

$$h(x_1)=h(x_2)⟺A(x_1-x_2)\equiv 0(\mathrm{mod}M).$$

令 $d=gcd(A,M)$，则该映射的像集大小为 $M/d$，每个可达值恰有 $d$ 个原像；仅当 $d=1$ 时，它才是 ${\mathbb{Z}}_M$ 上的一个排列。这个结论不能直接套到字符串的多项式哈希上。选择较大的质数作为模数便于在有限域中分析和运算，但并不会消除冲突。

多项式哈希冲突概率：

设哈希值域大小为 $M$，并假设 $q$ 个对象的哈希值相互独立且在 $[0,M-1]$ 中均匀分布，则出现至少一次碰撞的概率为

$$P_{\mathrm{coll}}=1-\prod _{i=0}^{q-1}(1-\frac{i}{M})\approx 1-\exp (-\frac{q(q-1)}{2M}).$$

当 $q\approx \sqrt{2M\ln 2}\approx 1.177\sqrt{M}$ 时，该概率约为 $1/2$。若希望碰撞概率至多为 $\epsilon$，则近似需要

$$M\ge \frac{q(q-1)}{-2\ln (1-\epsilon )},$$

当 $\epsilon$ 很小时即要求 $M$ 远大于 $q^2$，而不是要求 $M>\sqrt{q}$。一次碰撞会让对应的一对不同对象产生假阳性，并不意味着其它比较全部失效。

上述估计依赖独立、均匀的随机模型。固定模数、固定底数的多项式哈希可能被针对性构造；随机选择并隐藏底数或种子只能降低被构造的风险，不能提供确定正确性。

双模数多项式哈希：

使用两个模数分别计算多项式哈希，只有两路结果均相同时，才把两个字符串视为可能相同。

若两路计算的是同一个整数多项式 $H$，即使用相同的 base 和字符映射，且 $gcd(M_1,M_2)=1$，则由中国剩余定理可得

$$H(x_1)\equiv H(x_2)(\mathrm{mod}{M}_1),H(x_1)\equiv H(x_2)(\mathrm{mod}{M}_2)$$

等价于

$$H(x_1)\equiv H(x_2)(\mathrm{mod}{M}_1{M}_2).$$

若模数不互质，等效模数只能写成 $\mathrm{lcm}(M_1,M_2)$；若两路使用不同的底数，则它们不是同一个整数多项式，也不能用中国剩余定理合并。

只有在两路哈希可近似看作均匀且相互独立时，单次比较的碰撞概率才可近似相乘，生日界也才可按有效空间 $M_1{M}_2$ 估计。推广到更多模数时同样需要互质性或独立性等相应前提，不能无条件把各路概率直接相乘。

集合哈希：

判断两个序列排序后是否相同，本质上是判断两个多重集是否相同。

哈希做法：

两个多重集相同一定会得到相同摘要，反过来通常不成立。因此，构造确定性摘要可以视作增加用于排除“不相同”的必要条件。

例如此处，$n$ 个数平方和相等，是这 $n$ 个数一一相同的必要条件。

$n$ 个数相同 $\to n$ 个数平方和相等。

但是也会出现 $1^2+1^2+1^2+1^2+8^2=2^2+4^2+4^2+4^2+4^2=68$ 的情况。

可以继续增加立方和、四次方和等条件来排除一部分冲突，但只维护固定的少量幂和，尤其是 $k<n$ 时，通常仍可能被构造出冲突。在没有随机模型时，这里只有“能排除更多已知反例”的结论，不能自动表述为碰撞概率变小。

若多重集大小为 $n$，则在特征为 $0$，或有限域特征大于 $n$ 等能合法使用 Newton 恒等式的条件下，前 $n$ 个幂和可以确定各阶基本对称多项式，进而确定该多重集；只维护少量幂和时没有这一保证。

若维护前 $k$ 个幂和，预处理或逐个插入的总复杂度为 $O(kn)$，单点修改和一次区间摘要比较均为 $O(k)$；只有把 $k$ 视为常数时才能简写为每次 $O(1)$。

随机化

一种更容易分析的随机化方法是：选取大质数 $p$，为每个不同的值 $v$ 分配一个相互独立且在 ${\mathbb{F}}_p$ 中均匀的随机权值 $R(v)$，相同的 $v$ 始终使用相同的权值，并维护

$$F(A)=\sum _{a\in A}R(a)(\mathrm{mod}p).$$

对两个预先固定的不同多重集，若至少一个元素的出现次数之差不被 $p$ 整除，则在理想随机模型下 $F(A)=F(B)$ 的概率为 $1/p$。通常还要求随机种子不被对手预知；多路独立权值可以进一步降低误判概率。若出现次数之差可能是 $p$ 的倍数，或输入能根据种子自适应构造，则上述概率界不再成立。

多项式哈希做法：

update on 2025.4.20

2024 郑州 G 中使用了多项式哈希维护多重集摘要。设值域为 $[0,D]$，$c_v$ 表示值 $v$ 的出现次数，可以定义频次多项式

$$F_A(X)=\sum _{v=0}^D{c}_v{X}^v.$$

选取质数 $p$ 和随机点 $x\in {\mathbb{F}}_p$，维护 $F_A(x)modp$。若两个多重集不同、频次之差不全为 $p$ 的倍数且差多项式的次数不超过 $D<p$，则由非零多项式的根数界，单个随机点发生碰撞的概率至多为 $D/p$。使用多组模数或随机点时，只有各组随机选择相互独立，碰撞概率才能相乘。没有这些值域、模数和随机性前提，幂和摘要本身没有自动的小碰撞概率。

sum hash

上文的做法就是一种 Sum Hash。

Sum Hash 可以作为判断集合或多重集是否相同的概率摘要。

对于多重集 $S$，可以维护 $f(S)=\sum _{a\in S}h(a)$；求和时需要计入重复元素。若 $f(S_1)\ne f(S_2)$，则两者一定不同；若摘要相同，只能认为两者可能相同。

其中，$h(a)$ 的计算方式有很多，上文的 $x^a$ 就是一种。

更常见的随机化写法是直接令 $h(a)=R(a)$，其中 $R$ 是由隐藏种子确定的稳定随机映射。若值域可能包含 $0$，则不能无条件使用 $h(a)=a\times R(a)$：当 $a=0$ 时，该式恒为 $0$；在模 $2^{64}$ 的自然溢出下，偶数 $a$ 还会损失随机位。若在质数域中且 $a\ne 0$，乘以 $a$ 仍会保持均匀性，因此问题不在乘法本身，而在使用条件没有写明。直接使用 $R(a)$ 更通用。若要使用上文的 $1/p$ 误判界，求和还需满足对应的出现次数条件。

update on 2025.4.20：

2024 郑州 G 题引申了只取少量幂和的 sum hash 并不充分：当 $k=O(\log n)$ 时，仍能构造两组不同的多重集，使得 $\mathrm{\forall }i\le k,\sum _{j=1}^n{a}_j^i$ 相同。

隐藏种子后再做随机映射，可以阻止针对固定公开参数预先构造的部分数据，但这是一种概率保证，不能把有限个幂和变成确定充分条件。若需要维护区间加等操作，还必须证明所选摘要能够由区间信息正确更新；静态随机映射的 Sum Hash 一般不能仅由原摘要推出整体加值后的新摘要。

xor hash

xor 运算的一个性质：$a\oplus a=0,a\oplus b\ne 0(b\ne a)$。

所以使用 xor 可以很好地维护数字出现次数的奇偶性。

若某一个多重集内所有数字出现次数均为偶数次，那么 ${\oplus }_{a\in S}a=0$。

但是，${\oplus }_{a\in S}a=0$ 只是“所有数字均出现偶数次”的必要条件，并不充分。例如 $2\oplus 4\oplus 6=0$，但这三个数都只出现了一次。

可以为每个不同的值 $v$ 分配独立均匀的 $w$ 位随机串 $R(v)$，再维护这些随机串的异或和。对于一个预先固定、且确实存在奇数次元素的多重集，其摘要误为 $0$ 的概率为 $2^{-w}$。该结论依赖独立随机映射和固定输入；公开种子下的自适应构造不受此界保护。

xor hash 应用：

排列，是一个特殊的序列，其中每个数在 $[1,n]$ 中不重不漏的出现一次。

同一个长度的所有排列的异或和相同，所以可以预处理 $1\oplus 2\oplus \cdots \oplus n$。但是，直接比较原数值的异或和只是必要条件，即使序列长度为 $n$ 且所有值都在 $[1,n]$ 内也不充分。例如

$$1\oplus 1\oplus 1\oplus 2\oplus 2=1=1\oplus 2\oplus 3\oplus 4\oplus 5.$$

概率判定时，必须先确认序列长度为 $n$，并检查每个值都在 $[1,n]$ 内，再比较

$$\underset{i=1}{\overset{n}{⨁}}R(a_i)\text{与}\underset{i=1}{\overset{n}{⨁}}R(i),$$

其中 $R(i)$ 是相互独立的 $w$ 位随机标签。在这些前提下，任意固定的非排列至少有一个值的出现次数奇偶性与目标不同，误判概率为 $2^{-w}$。使用同一组标签完成 $Q$ 次固定查询时，总误判概率至多为 $Q/2^w$，不能把各次错误事件当作相互独立。若要求确定正确，应直接统计每个值的出现次数或使用 vis 数组判重。

xor hash 再扩展：

能用 xor hash 出现次数为偶数的情况，是基于 $a\oplus a=0$，也即是出现次数是 $2$ 的倍数。那如果现在需要判断出现次数是 $k$ 的倍数呢？

可以把异或推广为各位独立的模 $k$ 加法，使同一个标签累加 $k$ 次后得到 $0$。若标签有 $d$ 个 $k$ 进制位，一次运算需要 $O(d)$，通常可写成 $O({\log }_{k}U)$，其中 $U$ 是标签空间大小。

“所有出现次数都是 $k$ 的倍数”一定会使摘要为 $0$，反过来仍可能冲突。若 $k$ 为质数，并把每个值独立均匀地映射到 ${\mathbb{F}}_k^d$，则对任意固定的非零次数余量向量，误判为 $0$ 的概率为 $k^{-d}$；$k$ 为合数时，非零系数未必可逆，不能直接沿用这个概率界。随机映射只能给出相应模型下的概率保证，不能避免冲突。