awdec's Blog

哈希本质均为“单映射”，就是通过某些手段，将原数据变换成新数据。

若哈希在“单映射”的同时，越满足“双映射”，则哈希越“强”。

哈希表：

哈希不存在“冲突”的问题，从存储上，以下两种方法都解决了不同元素映射至同一个位置的问题。

但是在确定唯一位置的目的上，花费了额外的时间，导致在刻意构造下，效率和线性表一致。

在非特意构造下，可认为插入、删除、查询均为 $O (1)$ 。

开放寻址法：

此方法用于基本存储数据的基本数据结构还是线性表。

取一个模数 $M$ ，假设插入的数是 $x$ ，则 $f (x) = x mod M$ ，若 $f (x)$ 的位置上，已经有元素了，那么 $f (x) = f (x) + 1 mod M$ ，直到 $f (x)$ 位置上没有元素，将 $x$ 插入 $f (x)$ 的位置。

拉链法：

此方法用于基本存储数据的基本数据结构是链表和线性表（或者其它任意数据结构）。

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

事实上，开放寻址法和拉链法可通过修改哈希函数，优化效率。

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

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

cpp

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct Hash_Map {
    bool vis[N];
    int a[N], b[N];
    stack<int> q;
    Hash_Map() { memset(a, -1, sizeof a); }
    void clear() {
        while (q.size()) {
            auto now = q.top();
            q.pop();
            vis[now] = 0;
            a[now] = -1;
        }
    }
    const u64 s1 = rnd(), s2 = rnd(), s3 = rnd();
    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;
        while (vis[now] && a[now] != x) {
            now = (now + 1) % N;
        }
        return vis[now] && a[now] == x;
    }
    int get(u64 x) {
        int now = f(x) % N;
        while (vis[now] && a[now] != x) {
            now = (now + 1) % N;
        }
        if (!vis[now])
            q.push(now);
        vis[now] = 1, a[now] = x;
        return now;
    }
    int &operator[](const u64 x) { return b[get(x)]; }
};

多项式模数哈希：

h (a) = \sum_{i = 1}^{n} a_{i} b a s e^{i - 1} mod p

优点：

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

缺点：

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

自然溢出：

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

优点：

运算速度快，

缺点：

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

哈希冲突空间

考虑： $a \equiv x (\mod c)$ 。

冲突的情况即为同余方程解的数目。

a \equiv x (\mod c) \Leftrightarrow x = a + y c

若 $gcd (a, c) \neq 1$ ，令 $k = gcd (a, c)$ ，则 $x = k a^{'} + y k c^{'} \to \frac{x}{k} = a^{'} + y c^{'}$ ，即：解空间由 ${x}$ 变成了 ${\frac{x}{k}}$ ，若原本的冲突空间为 $[0, mod - 1]$ ，此时则为 $[0, \frac{mod - 1}{k}]$ 。

那么为了使冲突空间尽可能大，就要使 $gcd (a, c)$ 尽可能小，直接让 $gcd (a, c) = 1$ 即可，所以通常选取一个大质数作为模数。

多项式哈希冲突概率：

设模数为 $mod$ ，则映射集合为 $[0, mod - 1]$ 。

假设字符串随机分布，即哈希值随机分布（每次从 $[0, mod - 1]$ 中随机选一个数）。

根据“生日悖论”，在随机 $O (\sqrt{mod})$ 次后，有约 $\frac{1}{2}$ 的概率产生冲突。（实际上这个值是）

若产生冲突，则字符串哈希用于“判断两个字符串是否相同”的目的即失效。

所以在随机情况下， $mod$ 一般要超过 $\sqrt{字符串数目}$ 。

但是上述结论建立在随机的情况下，在实际场景中，往往可以通过对特定模数的特定构造，达到 $2$ 次即冲突的情况。

双模数多项式哈希：

即使用两个模数，分别进行多项式模数哈希，只有在两者结果均相同时，认为字符串相同。

$f (x_{1}) \equiv f (x_{2}) (\mod M_{1}), f (x_{1}) \equiv f (x_{2}) (\mod M_{2}) \Rightarrow f (x_{1}) \equiv f (x_{2}) (\mod M_{1} M_{2})$ 。

同样使用“生日攻击”的情况下，随机 $O (\sqrt{M_{1} M_{2}})$ 次后会有超过 $\frac{1}{2}$ 的概率冲突。

同样地，双模数可以推广到 $n$ 模数， $M_{i}$ 的冲突概率是 $p r (M_{i})$ ，则 $n$ 模数冲突的概率就是 $\prod_{i = 1}^{n} p r (M_{i})$ 。

集合哈希：

判断两个序列升序后是否相同。

哈希做法：

哈希的“单映射”就像是假言推理中的必要条件。如果能做到“双映射”那就是充要条件。

所以，构造哈希函数，也可以视作找必要条件的过程。

例如此处， $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$ 的情况。

因此，需要通过构造更多的必要条件，来尽可能地实现充要条件。

必要条件越多，哈希冲突的概率就越小。

此处，可以增加 $n$ 个数立方和相等作为第二个必要条件。

同样的，还可以增加四次方和、五次方和、六次方和等等。

时间复杂度取决于具体问题限制要求，如果静态不带修， $O (1)$ 即可维护。

随机化

如果只维护平方和，会出现形如 $1^{2} + 1^{2} + 1^{2} + 1^{2} + 8^{2} = 2^{2} + 4^{2} + 4^{2} + 4^{2} + 4^{2} = 68$ 的情况。但是可以引入随机化，给每一个元素随机地加上一个数。

$(1 + r d_{1})^{2} + (1 + r d_{1})^{2} + (1 + r d_{1})^{2} + (1 + r d_{1})^{2} + (8 + r d_{8})^{2}$ 和 $(2 + r d_{2})^{2} + (4 + r d_{4})^{2} + (4 + r d_{4})^{2} + (4 + r d_{4})^{2} + (4 + r d_{4})^{2}$

此时，再相等的概率就较小了。

实际上就是对每个元素再做一次哈希。

多项式哈希做法：

update on 2025.4.20

2024 郑州 G 补充了使用多项式哈希维护集合哈希的更加稳定做法。

其实也是 naive 的。

本质和序列哈希相同，将元素视作序列下标，维护 $\sum x^{a_{i}} mod M_{1}, \sum x^{a_{i}} mod M_{2}$ 即可。 $x$ 可以通过随机选取，并取多个。

sum hash

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

Sum Hash 用于判断集合是否相同。

对于集合 $S$ ， $f (S) = \sum_{a \in S} h (a)$ 。若 $f (S_{1}) = f (S_{2})$ 则认为 $S_{1} = S_{2}$ 。

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

还有一种更普遍的是： $h (a) = a \times r a n d (a)$ ，是为 $a$ 乘一个随机权值（相同的 $a$ 得到相同的权值）。

update on 2025.4.20：

2024 郑州 G 题引申了 $k$ 次方和的 sum hash 是错误的，说明了在 $k \leq O (\log n)$ 时，可以构造两组不同的集合，使得 $\forall i \leq k, \sum_{j = 1}^{n} a_{j}^{i}$ 相同。

但是如果不带修的话，可以为序列每一个初始值随机映射一个权值，再进行 $k$ 次方和 sum hash，因为 hack 是需要构造的。

2024 郑州 G 题需要维护区间加，这就使得序列两个数的差值不能发生改变，在此条件下，hack 仍能构造。

xor hash

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

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

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

那么反过来， $\oplus_{a \in S} a = 0$ 是集合内所有数字出现次数为偶数的必要条件，容易构造不充分的情况： $2 \oplus 4 \oplus 6 = 0$ 。（当然，本质上还是某个数可以表示成若干个数的异或和）

同样地，仍然可以借助随机化的策略，将集合中每个数映射到一个随机值上，再使用异或和为 $0$ 判断是否均出现偶数次。

xor hash 应用：

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

并且同一个长度的所有排列的异或和相同。即：排列的异或和只和排列的长度有关。所以 $O (n)$ 即可预处理出所有长度的排列的异或和。

判断一个序列是不是一个排列，就可以通过序列的异或和和对应长度排列的异或和比较得到。

不过同样的，异或和会出现相同的不充分情况： $1 \oplus 1 \oplus 2 \oplus 6 = 1 \oplus 2 \oplus 3 \oplus 4$ 。解决办法和上文相同，给每个数随机映射一个值即可。

xor hash 再扩展：

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

同样地，只需要构造一种运算，使得 $a \oplus \dots \oplus a = 0$ （共 $k$ 个 $a$ 进行二元运算）

异或是二进制的不进位加法，所以只要把二元运算定义成 $k$ 进制下的不进位加法即可。但是计算 $k$ 进制下的不进位加法需要 $O (\log_{k} n)$ 的时间。

同样将每个数随机映射到一个数上，以避免冲突。

哈希表： ​

开放寻址法： ​

拉链法： ​

多项式模数哈希： ​

优点： ​

缺点： ​

自然溢出： ​

优点： ​

缺点： ​

哈希冲突空间 ​

多项式哈希冲突概率： ​

双模数多项式哈希： ​

集合哈希： ​

哈希做法： ​

随机化 ​

多项式哈希做法： ​

sum hash ​

xor hash ​

xor hash 应用： ​

xor hash 再扩展： ​