Universal Classes of Hash Functions(1977)

#Hash function

June 10, 2023

値の保存と参照からなる任意のリクエストの系列を、系列長の時間計算量で処理できるハッシュ関数と連想配列を示す。求めるハッシュ関数の集合があるとき、各ハッシュ関数の時間計算量の平均がリクエストの系列長に等しくなる。

はじめに、ハッシュ値の衝突回数を見積もる。 $f$を集合$A$から集合$B$へ写像するハッシュ関数とする。 $x, y\in A$として、ハッシュ値の衝突回数を次の$\delta$で定義する。 $$ \delta_f(x,y)= \begin{cases} 1&\text{if}\ x\neq y\ \text{and}\ f(x) = f(y)\\ 0&\text{otherwise} \end{cases} $$

$H$を任意のハッシュ関数の集合とすると、以下の不等式が成り立つ$x, y$が必ず存在する。 $$ \delta_H(x,y)>\frac{|H|}{|B|}-\frac{|H|}{|A|} $$

上の命題を証明する。 $a=|A|,\ b=|B|$とする。各$i\in B$について、$A_i$を$f$によって$i$に写像される$A$の要素の集合とし、$a_i=|A_i|$とおくと、 $$ \delta_f(A, A) = \sum_{i\in B}\delta_f(A_i,A_i)=\sum_{i=B}(a^2_i - a_i) $$ である。この値が最小値になるのは、すべての$i$について$a_i$が等しいときであり、$a_i=a/b$のときである。よって $$ \delta_f(A,A)\geq a^2(1/b-1/a) $$ であるから $$ \delta_H(A, A)\geq a^2\left(\frac{|H|}{|B|}-\frac{|H|}{|A|}\right) $$ である。 $x, y$のとりうる組合せは$a^2$個あり、$\delta_H(x,x)=0$であるから、鳩の巣の原理より命題が成立する。

任意の$x, y$について$\delta_H(x,y)\leq |H|/|B|$が成立するハッシュ値の集合を$\text{universal}_2$とよぶ。 $\text{universal}_2$がリクエスト系列を線形時間計算量で処理できることを証明する。 $\delta_H(x,y)\leq |H|/|B|$は、任意の$A$の要素のペアをとりだしたとき、$1/|B|$番目より後のハッシュ関数とは衝突することはないとも言い換えられる。

$S$を$A$の部分集合、$f$を$\text{universal}_2$からランダムに選んだ関数とすると、$\delta_f(x,S)$の平均値は$|S|/|B|$以下である。これは、$\sum_H\delta_f(x,S)=\sum_{y\in S}\delta_H(x,y)$であり、$\text{universal}_2$の定義から $$ \begin{align} \frac{1}{|H|}\sum_{y\in S}\delta_H(x, y) &\leq \frac{1}{|H|}\sum_{y\in S}\frac{|H|}{|B|}\\ &=\frac{|S|}{|B|} \end{align} $$ が成立するからである。

次にリクエストの系列の時間計算量を考える。衝突したキーを隣接リストで管理することを想定し、既に連想配列にキーの集合$S$が格納されている状態における$x$の処理にかかる時間計算量を$1+\delta_f(x, S)$とする。このとき、前段落で証明した命題より、$\text{universal}_2$からランダムに選んだハッシュ関数を$f$について、 $k$個の格納処理を含む長さ$r$のリクエスト系列を処理するためにかかる空間計算量の期待値は、$r(1+k/|B|)$以下である。このとき、$|B|$を大きくとれば空間計算量の期待値を1にすることができる。

論文では、3種類の$\text{universal}_2$が紹介されている。

雑記

写像先の空間を大きくしなければ衝突を減らせないという月並な結論に落ち着いている。