Rolling Hash
概要
何かの列があるときに, これのハッシュを取りたい. 列の要素は何かしらの方法で整数に変換されてるとする.
\[\langle c_1, c_2, \ldots, c_k \rangle\]
ここで適当な数 \(a\) を基数として, 次の値をハッシュとする.
\[H(c) = \sum_{i=1}^k c_i a^{k-i} = c_1 a^{k-1} + c_2 a^{k-2} + \cdots + c_k a^0\]
特に空列のハッシュ値は \(0\) とする. 列が等しいことを見るのにこのハッシュ値の値が等しいかをチェックする.
この値は指数を含むので, すぐに膨大になる. 適当な大きな素数 \(p\) を用意しておいて \(\bmod p\) で計算するのが普通.
値の追加と削除
数列の頭または末尾に値を一つ追加または削除することは上の値を注意深く計算すれば, 再計算の必要なく高速に計算出来る. 特に末尾に一つ追加する場合が効率が良い形をしていて, 列 \(c\) のハッシュ値が \(H(c)\) とあるときに, この末尾に \(x\) を追加したもののハッシュ値は次で求まる.
\[H(c \ast x) = H(c) \times a + x\]
テク
ではその基数 \(a\), mod \(p\) に何を使うかには自由度が残っている. \(p\) はハッシュの大きさを決めるものなので大きければ大きいほど良い. \(a\) はもし文字列から文字を削除する場合には \(a^{-1}\) が求まるほうが良いので, \(p\) と互いに素であるのがよい. 適当な素数にしておけばよい. \(p\) も大きな素数にしておけばよい.
この辺の話は 安全で爆速なRollingHashの話 - Qiita を読み込むのが良さそう.
- 悪意ある人がハッシュ衝突を狙うような場面では基数をランダムに取ることで安全になる
- Codeforces の hack 対策
- \(p\) にメルセンヌ素数を使うと MOD 演算をビット演算で高速化可能
- MOD 演算は遅い
といったことが書いてある.