Hash ​

Hash算法的本质 ​

将信息映射到一个 $d$ 维向量上（哈希值），通过判定向量的相等，从而判定信息的相等。

最为常见的，$d=1$，此时哈希值就是一个数。

数值映射hash ​

在理想概率均匀的情况下，可以认为冲突概率是 $1/p$。

法一：模质数 ​

核心思想：
将特别大的整数（需要用高精度存储的）映射成小整数。

常见应用：

• 判断大整数是否相等
• 可以方便的处理 $+,-,\times,/$ 等计算式的结果
• 是绝大多数hash的基础

法二：xorshift ​

核心思想：
将任意正常大小的整数映射成较大整数（通常是 ull）。

标准实现：

ull shift(ull x) {
    x = x * rnd1 + rnd2;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

ull shift(ull x) {
    x = x * rnd1 + rnd2;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

法三：多项式函数映射 ​

核心思想：
将任意正常大小的整数映射成较大整数（通常是 ull）。

运用： 一般可以和 xorshift、自然溢出一起使用，效率都比较高，且冲突概率非常小。

法四：赋rand值 ​

核心思想：
将小整数映射成较大整数（通常是 ull）。

集合映射hash ​

法一：xor hash ​

核心思想：
将集合里的数用数值映射hash以后再 xor 起来。

常见运用：

• 处理涉及到出现次数奇偶性的问题
• 处理差分更方便：树上路径，或是序列的子段

法二：加法hash ​

核心思想：
将集合里的数用数值映射hash以后再加起来。

常见运用：

• 处理涉及到出现次数是倍数的问题
• 同样可以处理差分，略麻烦一些

字符串hash/多项式hash ​

核心思想：
将其看作一个 $P$ 进制数，进行数值映射。

注意：

• 必须保证数的每一位值是正整数
• 应保证 $P$ 大于每一位上取的数值
• 如果是考虑子串的话，一定要用自然溢出或双模

冲突概率：

• 两个长为 $n$ 的串冲突概率：$n/p$
• $x$ 个长为 $n$ 的串不冲突概率：$(1-n/p)^{x(x-1)/2}$

树hash ​

树hash都是针对有根树的hash。

一个点的hash值等于 $1 +$ 子结点hash值组成的集合hash。

可以利用换根实现无根树hash。

矩阵hash ​

利用向量乘矩阵加速的性质，随机一个向量即可。

例题 ​

• P2312：大整数映射
• P1224：比较难想，尤其是 $k=3$ 的情况
• P8819