ハッシュ化とは

• 任意サイズのデータから固定長の値を得るもの。
• 実物の代わりにハッシュを用いることで計算量の削減ができる。
• ハッシュを使って、例えば一致性判定ができる

ローリングハッシュ

• ローリングハッシュは数列をハッシュ化する。
• ローリングハッシュの計算方法
  • 数列 $(x_0, \ldots, x_{n-1})$ に対して、$x_0 b^{n-1} + x_1 b^{n-2} + \cdots + x_{n-2} b + x_{n-1} \bmod p$ をハッシュ値とする。
    • mod $2^{61} -1$ にして、base $b$ をランダムに取るのがよいとされている。
      • 安全で爆速なRollingHashの話 #競技プログラミング - Qiita
    • ある $i$ で $x_i = 0$ だとだめ。
      • 例えば $(0, 0,0,1)$ と $(0, 1)$ のローリングハッシュが同じになってしまうため。
    • 多項式を評価したものと見るとよさげ。
    • 添字と指数部分を足したら $n-1$ になる（畳み込みのノリ）
• ローリングハッシュでできること
  • 2つの数列が一致
  • 連続部分列のハッシュ値の計算
    • 前処理として、$(x_0,\ldots, x_{i-1})$ のハッシュ値 s(i) を持っておく
      • 累積和みたいなもの
      • prefix のハッシュ値
    • $(x_i, \ldots, x_{j-1})$ のハッシュ値は $s(j) - b^{j-i} s(i)$ で求まる。(mod p で計算)
      • 導出
  • 2つの数列を連結させたときのハッシュ値の計算
    • 2つの数列 $x, y$ に対して、$x$ と $y$ を連結させた数列のハッシュ値は $b^{|y|} H(x) + H(y)$ である。
    • この意味でローリングハッシュはモノイドをなす (参考: モノイド)
      • つまりセグ木に乗る
• ローリングハッシュは文字列の一致性判定でよく用いられる
  • 文字列を数列に変換して使う。例えば a を 1、b を 2、…と変換する（0には変換しないように注意）
  • 詳細: 文字列アルゴリズム

2次元ローリングハッシュ

$\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} a_{i,j} b^{n-i-1} c^{m-j-1}$

参考: ラビンカープ法のおはなし+二次元のロリハいいぞ | 東京工業大学デジタル創作同好会traP

Zobrist Hash

• Zobrist Hash は集合をハッシュ化する
• Zobrist Hash の計算方法
  • 集合の各要素に対して、ランダムな整数を割り当てる。割り当てた整数の総 xor が Zobrist Hash
• Zobrist Hash でできること
  • 2つの集合の一致判定
    • $H(A) = H(B)$ であれば、$A=B$ が期待できる。
      • $H(A) = H(B)$ であっても、$A\neq B$ なこともある。
  • 要素の追加・削除
    • $x \notin A$ のとき、$H(A\cup\{x\}) = H(A) \oplus H(\{x\})$
    • $x \in A$ のとき、$H(A\setminus\{x\}) = H(A) \oplus H(\{x\})$
  • 対称差
    • $H(A \triangle B) = H(A) \oplus H(B)$
• 応用例
  • チェス盤のハッシュ化
    • チェス盤を (コマの種類, コマの色, 駒の位置) の集合とみなす。この集合を Zobrist Hash でハッシュ化する
      • コマの種類6通り×コマの色2通り×駒の位置64通り = 768通りに対してランダムな整数を割り当ててxor を取ることで、チェス盤のハッシュ化ができる
    • コマを1つ動かした場合、新しいハッシュ値は O(1) で計算できる
      • 動かす前のコマの状態を引いて、動かしたあとのコマの状態を足す（xor の世界では足し算も引き算も xor をすればよい）
      • 差分更新が簡単に計算できる
    • 参考: 集合をハッシュする (Zobrist hashing) | 東京工業大学デジタル創作同好会traP
• 多重集合で Zobrist Hash を考えると、各要素の重複度の偶奇が一致していれば一致している判定になる。