Reading: Performance in Practice of String Hashing Functions

Performance in Practice of String Hashing Functions は boost の hash function を決める際の根拠となっている論文みたいなので読んでみました。

Conclusions

Introduction

Classes of hashing functions

s = $c_1$ $\cdots$ $c_m$ を m 文字の文字列、$v$ を seed、$h_i$ を i 文字を試行した後の hash value として、以下の形式で表せる。

$$ \begin{cases} h(s, v) = \newline \quad set \ h_0 \leftarrow init(v) \newline \quad for \ each \ character \ c_i \ in s, \newline \qquad set \ h_i \leftarrow step(i, h_{i-1}, c_i) \newline \quad return \ h = final(h_m, v) \end{cases} $$

上式は以下の計算ステップで説明できる。

  1. 関数 init を v に適用して $h_0$ の初期値を得る。
  2. 各 step $h_i$ は i 番目の関数 step で、hash 値はそれまでに計算された hash 値と現在の文字で計算される。
  3. 結果の hash 値は v と $h_m$ を final 関数に適用した値になる。

init, step, final は例えば以下のように定義できる。

$$ \begin{eqnarray} init(v) &=& 0 \newline step(i, h, c) &=& h + c \newline final(h, v) &=& h \newline \end{eqnarray} $$

汎用目的の hash 関数は以下の性質を満足するべきだ。

hash 関数の構成

以下の観点を考慮する。

shift-add-xor class の hash 関数を以下に定義する。

$$ \begin{eqnarray} init(v) &=& v \newline step(i, h, c) &=& h \oplus (L_{L}(h) + R_{R}(h) + c) \newline final(h, v) &=& h || T \newline \end{eqnarray} $$

shift magnitudes L と R を 32 bit 空間で構成することで適切な選択が与えられ、hash 値がより一様に分布する可能性を高める。この論文の実験では L = 5, R = 2 を使った。

4 <= L <=7 (大きな hash 値を生成するのに少しの文字しか必要としないので) と 1 <= R <= 3(最初の数文字の効果は少ないため) ではたいした違いはない。

実験では文字セットは ASCII で、7 bit だったことに注意。

この hash 関数は以下の理由で効率的である。

テーブルサイズが素数であることや何らかの方法で注意深く選ばれたものであることを要求していない点を注意しておきたい。 この hashing 関数はあらゆるテーブルサイズで有効なのである。

step 関数を

$$ step(i, h, c) = h \oplus (L_{L}(h) \oplus R_{R}(h) \oplus c) $$

ではなく、上述の定義にしたのを疑問に思う読者もいるかもしれないが、shift-xor-xor class は uniform ではないのだ。 理由は完全には判明していないが、加算と exclusive OR が必要なようだ。

文字列の hash を計算するのに本質的には 2 つの方法がある。1つは shift-add-xor のように、直接文字列を文字列のビット列にするもの。 もう一つは、文字列を数値に変換し、それから数値向けの hash 関数を適用するもので、例えば次の関数がある。

$final(h, v) = ((v \times h) || p) || T$

ここで p は巨大な素数である。文字列の変換と hashing をすることで shift-add-xor より高速にできる可能性が低くなるだろう。

他の文字列 hashing 関数

multiplicative な手法で以下のものがある。

$$ \begin{eqnarray} init(v) &=& 0 \newline step(i, h, c) &=& h \times r + c \newline final(h, v) &=& ((v \times h) || p) || T \end{eqnarray} $$

上式の p は巨大な素数で、r は radix とする。

上式の派生型として、P を異なる素数の列として以下の式も利用可能である。

$$ \begin{eqnarray} init(v) &=& 0 \newline step(i, h, c) &=& h + P_i \times c \newline final(h, v) &=& ((v \times h) || p) || T \end{eqnarray} $$

これらの hash 関数をテストした結果、uniform であった(radix r は 2 のべき乗ではない)。これらの hash 関数は adversarial attack 耐性があるので、おそらく universal でもある。よって幅広く適用可能である。

Pearson が提唱した以下のアルゴリズムもある。

$$ \begin{eqnarray} init(v) &=& 0 \newline step(i, h, c) &=& A_{h \oplus c} \newline final(h, v) &=& h \end{eqnarray} $$

上式の A は 256 個の異なる 8 bit の値で、ランダムに交換可能であり、$A_{h \oplus c}$ は A の $h \oplus c$ 番目の値を意味する。このアルゴリズムは高速だけども 8 bit の hash 値しか計算できない。

他の興味深い hashing 関数に

$$ \begin{eqnarray} init(v) &=& v \newline step(i, h, c) &=& c \oplus (L_{L}(h) \lor (R_{32-L}(h) \land MASK)) \newline final(h, v) &=& h || T \end{eqnarray} $$

というものがある。shift-add-xor と同程度の計算量なので同じぐらいの計算速度であるが、若干攻撃に弱い。

Comments

comments powered by Disqus