ハッシュ化を高速化したい！

はじめに

皆さんも一度は経験があると思います。ハッシュ化を高速化したい...！
私もPythonでのhash()を使用してハッシュ化していたのですが、もっと高速にできないかと思いアルゴリズムを調べてみました
今回のアルゴリズムは多項式ハッシュです。ちなみにPythonのhash()ではSipHash-2-4が使用されています

多項式ハッシュのアルゴリズム

アルゴリズムは以下の数式で表され、文字列の長さをNとした時、計算量は $O(N)$となります

Hash(S) = (S_1 × B^{N-1} + S_2 × B^{N-2} + ... + S_N × B^0) mod M

1つ目の数値に対してBをかけて、その結果と2つ目の和にBをかけて・・・を繰り返していくとも考えられます

それぞれの値について

• $B$：基数
  • 集合よりも大きい数とする (英小文字が対象であれば26より大きい数)
• $M$：モジュロ値
  • 大きい数 (小さい数だと余りが一致する可能性が高まる)
  • 素数 (素数でないと周期性が生じる可能性がある、 $B^{20} \equiv B^{0} mod(100)$のようになってしまう)
• $S_i$：
  • 文字列の各文字を数値化したもの (ASCII値などに変換する)

実装例（Python）

$B$の累乗を求める際は、繰り返しの際に合わせて計算しておくと高速化できます

def polynomial_hash(s, b=31, m=10**9 + 7):
    hash_value = 0
    b_pow = 1
    
    for c in s:
        hash_value = (hash_value + ord(c) * b_pow) % m
        b_pow = (b_pow * b) % m
        
    return hash_value

このアルゴリズムの何が良いの？

• $O(N)$でハッシュ計算可能
• 一度、全体ハッシュを計算をしていると部分ハッシュは$O(1)$で計算可能

やはり、部分ハッシュを$O(1)$で求められるのは便利だなと思いました
部分文字列(長さ$K$)の比較を繰り返していく($Q$回)と$O(K*Q)$もかかってしまいますが、このアルゴリズムでハッシュ化し比較すると$O(N+Q)※$で済みます
※全体ハッシュの計算$O(N)$ + 部分ハッシュの計算$O(1)$ * ハッシュ(数値)同士の比較$O(1)$ * 繰り返し回数$O(Q)$

最後に

今回はシンプルなハッシュ化アルゴリズムでしたが、他にもセキュリティに強いハッシュ化アルゴリズムなどもあるので、そちらも調べていきたいなーっと思います！