哈希

· · 算法·理论

多项式哈希

用于快速判断两个序列是否相同。

对于长为 n 的序列 a_i,选定底数 B 和模数 M 后,定义 a_i 的哈希值为

\text{HASH}(a_i)=\left(\sum_{i=1}^n a_i \times B^{i-1}\right) \bmod M

多项式哈希是滚动的过程,因此可以对 a_i 的每个前缀预处理一个前缀哈希 h_i=\text{HASH}(a_{[1,i]})。此时有

\text{HASH}(a_{[l,r]})=h_r-h_{l-1} \times B^{r-l+1}

另外,多项式哈希是一种半群信息,可以配合线段树等数据结构。

树哈希

用于快速判断两棵树是否同构。

对 u 所在子树,定义其哈希值为

\text{HASH}(u)=1+\sum_{v \in \text{son}(u)} f\left(\text{HASH}(v) \right)

其中 f 为 \mathbb{N} \to \mathbb{N} 的一个映射。

这种哈希容易换根,因此无根树同构问题可以转化为集合哈希。

集合哈希

用于快速判断两个集合是否相同。

Sum Hash

对于集合 S,选定模数 M,定义其哈希值为

\text{HASH}(S)=\sum_{x \in S} f(x)

其中 f 是一个 S \to \mathbb{N} 的映射。

Xor Hash

对于集合 S,定义其哈希值为

\text{HASH}(S)=\bigoplus_{x \in S} f(x)

其中 f 是一个 S \to \mathbb{N} 的映射。

多用于一些特殊情形,如与奇偶性相关的问题。

f

上文提及的 f 可以如下设计:对于每个整数,将其随机映射到 [0,2^{64}) 内的一个整数。哈希表维护。

其他

P6688。

将区间减去最小值。定义集合 S 的哈希值为 \text{HASH}(S)=\left(\sum \limits_{x \in S} g^x\right) \bmod M。

线段树维护之,复杂度 O(q \log n)。submission。

P10992。

定义 p_i 为 i 之前该位置字符最后一次出现的位置,对序列 i-p_i 做多项式哈希,可以滚动。

二分答案,滑动窗口扫两遍判定,复杂度 O(n \log n)。submission。

CF1479D。

单次询问考虑二分答案,用 Xor Hash 来判定。

对值域建可持久化线段树,每个节点存一棵树,查询先差分开,然后线段树上二分。复杂度 O(q \log n)。

CF452F。

枚举等差中项,在值域上等差数列转化成一个回文串。

线段树维护正反哈希判定。O(n \log n)。