ローリングハッシュ入門：仕組み・実装・応用と衝突対策（Rabin–Karp・rsync・コンテント定義チャンク）」
エバープレイ編集部概要
ローリングハッシュ（rolling hash）は、文字列やバイト列の区間（スライディングウィンドウ）に対し、前の区間の計算結果を使って次の区間のハッシュ値を定数時間で更新できる種類のハッシュ関数です。文字列探索や差分検出、データ重複排除、コンテント定義チャンク（CDC）など多くのアルゴリズムで中心的に使われます。代表的な例として Rabin–Karp アルゴリズムや rsync の差分検出、Rabin fingerprint に基づくチャンク分割などがあります。
基本原理（多項式ハッシュ）
最も広く使われるローリングハッシュは多項式ハッシュです。長さ m の文字列 s[0..m-1] に対して、基数 B（base）と大きな法 M（modulus）を選び、次のように定義します。
h(s) = (s[0]*B^{m-1} + s[1]*B^{m-2} + ... + s[m-1]*B^{0}) mod M
ここで s[i] は文字の数値化（例えば ASCII 値やバイト値）です。この表現だと、左端の文字が最上位の重みを持ちます。ウィンドウを一文字右にスライドして新しい文字 t が末尾に入るとき、ハッシュ h' を次の式で更新できます。
h' = ((h - s[0]*B^{m-1}) * B + t) mod M
この式には事前計算した B^{m-1}（高次の重み）が必要ですが、計算は定数時間で行えます。これが「ローリング（転がす）」と呼ばれる所以です。
スライディング更新の注意点
減算後は負になる可能性があるため、言語実装では mod を取るか、M を足して正に直す必要があります。
B^{m-1} は事前に powB = B^{m-1} mod M として計算しておきます。複数長さで使う場合は累乗配列を用意します。
M は素数を選ぶのが一般的です。典型的には 10^9+7 や 10^9+9 といった 32-bit 級の素数、または衝突確率をさらに下げるために 64-bit の大きな素数（例：2^61-1 など）を使います。
衝突確率と理論的根拠
2 つの異なる文字列が同じハッシュ値を持つことを衝突（collision）と呼びます。多項式ハッシュの衝突確率の解析には Schwartz–Zippel のような多項式の根に関する補題が使えます。異なる長さ m の文字列に対する差を表す多項式の次数は最大 m-1 であり、ランダムに選んだ基数 B（もしくはランダムに選んだ法 M 上の係数）に対して、B がその多項式の根になる確率は最大 (m-1)/M で抑えられます。従って、M を十分大きく取れば衝突確率は小さくできますが、完全にゼロにはなりません。
実装上の実務的ポイント
整数オーバーフロー対策：言語によっては乗算時に 64 ビット以上のオーバーフローが発生します。安全に実装するには大きめの整数型を使うか、明示的にモジュロ演算を入れます。モジュロ演算は高速性に影響するため、より高速なトリックとして 64-bit の符号なし整数の自然なオーバーフロー（mod 2^{64}）を利用する実装がよく使われます。ただし、mod 2^{64} は数学的には素数での剰余と性質が異なるため、衝突特性が変わります。
Mersenne 素数 2^{61}-1 の利用：2^{61}-1 のような特殊な素数は、高速な剰余計算トリックが使えます。例えば 128 ビット乗算の結果 x に対して、x mod (2^{61}-1) は (x & M) + (x >> 61) の繰り返しで求められ、必要ならさらに M を引くことで正規化できます（ここで M は 2^{61}-1）。この方法は高速で良好な衝突特性を示し、競技プログラミングや実務でもよく使われます。
基数 B の選び方：B は 256 や 911382323 といった任意の値が使えますが、衝突低減のためにランダムに選ぶ（初期化時に乱数で決める）ことが推奨されます。固定値を使うと特定の敵入力で衝突を誘発されやすくなります。
二重ハッシュ（double hashing）：衝突耐性を上げる簡単な方法は別の基数／法で 2 つのハッシュを取り、両方一致したときのみ候補とすることです。ほとんどの実用ケースで十分信頼できる結果が得られます。
検証ステップ：Rabin–Karp のような用途では、ハッシュ一致は「候補」として扱い、衝突の可能性を排除するために実際の文字列比較で検証するのが一般的です。これにより誤検出を完全に防げます。
代表的な応用例
部分文字列探索（Rabin–Karp）：長いテキスト中から長さ m のパターンを探すとき、テキストの各長さ m の区間のハッシュをローリングに計算していき、パターンハッシュと一致した位置のみ実際の比較を行うことで平均 O(n+m) 付近の性能を得ます（悪いケースで O(nm) になる可能性もあるため、ハッシュ衝突の扱いが設計上重要です）。
差分同期（rsync の弱いチェックサム）：rsync は転送元と転送先でブロック単位に「弱い」ローリングチェックサム（簡単な加算と重み付け和）を使って候補の一致を早期発見し、候補に対して強いハッシュ（例えば MD5/MD4 など）で最終確認を行います。弱いチェックサムは更新が非常に速く、ブロック位置に対するローテーション検出に適しています。
コンテント定義チャンク（Rabin fingerprint ベースの CDC）：ファイルを固定長で区切るのではなく、コンテンツに依存して境界を決める手法があります。Rabin fingerprint（GF(2) 上の多項式ハッシュ）を用い、ハッシュの下位ビットが特定パターン（例：下 k ビットがゼロ）になる位置を境界にすると、挿入や削除に対してロバストなチャンク分割が可能で、重複除去や差分転送で有利になります。
高速なストリーム比較や重複検出：大規模データに対する近似一致検索、スライディングウィンドウを使った特徴抽出などにも使われます。
典型的な擬似実装（手順）
初期化：基数 B と法 M を決め、pow = B^{m-1} mod M を計算する。
最初のハッシュ計算：h = sum_{i=0}^{m-1} s[i]*B^{m-1-i} mod M を計算。
スライド更新（左から右へ一文字ずつ）：
h = h - s[old]*pow ; // pow = B^{m-1}
if h < 0 then h += M ;
h = (h * B + s[new]) mod M ;
各位置でハッシュを比較し、一致したら必要に応じて実際のバイト列比較で検証する。
実務でよく使われるトリックと最適化
64-bit の自然なオーバーフローを利用：C/C++ で unsigned long long を使い、乗算の結果をそのまま保持すると 2^{64} で剰余を取ったことと同等になります。衝突特性は変わりますが、実用上は十分なことが多く、高速です。
2^{61}-1 のような Mersenne 素数の利用で高速化：この種の素数は高速に剰余を計算できるため、精度と速度のバランスが良いです。競技プログラミングやパフォーマンスを要求される実務実装で有用です。
複数ハッシュの並列計算：SIMD やマルチコアを使って複数のハッシュを同時に計算すると、二重ハッシュをとる際のコストを抑えられます。
境界条件の最適化：長さ m が固定である場合、pow を再利用することで毎回の累乗計算を回避できます。
代表的な設計上の落とし穴
固定基数＋固定法の組合せは、攻撃者が悪意のある入力を作成しやすくなる（ハッシュ衝突を誘発する）ため、公開 API やセキュリティに関与する用途では注意が必要です。乱数で基数を初期化するか検証手順を入れるべきです。
ローリングハッシュ自体は暗号的ハッシュではない：衝突耐性や予測困難性は限定的なので、認証や暗号的整合性チェックには向きません。強い整合性確認が必要な場合は SHA-2/3 などの暗号学的ハッシュを併用してください。
実世界での利用例（補足）
rsync：差分同期でブロック単位に弱いローリングチェックサムを使って候補領域を検出し、強いハッシュで確認します。これにより少ないデータ転送で同期できます。
コンテンツストア／バックアップ：類似区間を結合して保存するための重複除去で CDC（Rabin fingerprint ベース）を使う例が多くあります。挿入や削除を行っても境界の多くが保たれるため、差分が小さい場合に効率的です。
テキスト検索やプログラミング言語処理系：高速なパターンマッチングの第一段階でローリングハッシュを使い、候補を絞ってから確定判定を行う設計はよく見られます。
まとめ
ローリングハッシュは、スライディングウィンドウに対して高速にハッシュを更新できる強力な技術であり、文字列探索、差分検出、重複除去、コンテンツ定義チャンクなど幅広い場面で使われます。実装では基数と法の選択、オーバーフローや負数処理、衝突対策（検証や二重ハッシュ）が重要です。また、暗号的目的には向かないため、必要に応じて強いハッシュや検証ステップを組み合わせてください。
参考文献
Rabin–Karp algorithm (Wikipedia)
String hashing — CP-algorithms（実装と注意点）
投稿者プロフィール
