Storing a Sparse Table with O(1) Worst Case Access Time(1984)
April 8, 2023単射のハッシュ関数は完全である。完全ハッシュ関数により、衝突することのないハッシュテーブルのデータ構造と計算時間量の証明を示す。 データ構造は、はじめに、\(U(|U|=m)\)の部分集合\(S\)(\(|S|=n\))の要素\(x\)をハッシュテーブルに格納するとき、ある\(U\)の要素\(k\)を使った関数\(f(x)=(kx\mod p)\mod n\)で\(x\)を格納するブロック\(W_j(0\le j < n)\)を決める。 \(p\)は\(p=m+1\)の素数である。 次に\(U\)の要素\(k'_j\)をもちいた関数\(g(x) = ((k'_jx) \mod p)\mod |W_j|^2\)で、\(x\)のエントリを特定する。 データ構造の証明は、\(f, g\)によって重複なくエントリを特定できる\(k\), \(k'_j\)があることを示す。
\(|W|=r, W\subseteq U, k\in U, s\ge r\)とおき、\(B(s,W,k,j)\)を、関数\(f(x)=(kx\mod p)\mod s\)で\(j(0\le j< s)\)へ写像される\(W\)の要素数とする。より正確には、\(B(s,W,k,j)=|\{x|x\in W \text{and} (kx \mod p)\mod s = j\}|\)である。 このとき、以下の補題がなりたつことを証明する。 $$ \sum^{p-1}_{k=1}\sum^{s-1}_{j=0}\binom{B(s,W,k,j)}{2}<\frac{(p-1)r^2}{s} $$ 左辺は、\(x, y\in W, x\neq y, 1\le k < p\)である $$ (kx\mod p)\mod s = (ky \mod p)\mod s $$ をみたすペア\((k, \{x, y\})\)の数である。 \(x\)と\(y\)を固定すると、ペアの要素になりえる\(k\)の条件は、\(p\)が素数なので $$ k(x-y)\mod p\in \{s, 2s, 3s,\dots,p-s,p-2s,p-3s,\dots\} $$ である。\(\mod p\)において\(x-y\)は逆元が存在するので、右側の集合の要素と1対1に対応する\(k\)がある。 したがって、条件をみたす\(k\)の数は\(2(p-1)/s\)以下である。 また、\(x, y\)の選び方が\(\binom{r}{2}\)であるため、不等式が成立する。
\(s=r^2\)のとき、補題より $$ \sum^{p-1}_{k=1}\sum^s_{j=1}\binom{B(s,W,k,j)}{2} < (p-1) $$ が成立するため、すべての\(j\)において\(B(r^2, W,k',j)< 1\)である\(k'\)が存在する。 よって、始域を\(W\)とすると\(g(x)=(k’x\mod p)\mod r^2\)と\(x\)は1対1の対応関係になる。
論文のリンク
雑記
論文では\(1\le j \le s\)だが、\(\mod s\)ではつねに\(j\neq s\)なので、\(0\le j < s\)とした。
もとの補題は $$ \sum^s_{j=1}\binom{B(s, W, k, j)}{2} < \frac{r^2}{s} $$ であり、 $$ \sum^{p-1}_{k=1}\sum^{s-1}_{j=0}\binom{B(s,W,k,j)}{2}<\frac{(p-1)r^2}{s} $$ を証明することで、もとの補題を証明することにしていた。 逆の証明がないので、もとの補題を使わないことにした。
一つの関数ではなく、\(f\)と\(g\)を使うのは、\(n^2\)だと必要な空間が大きすぎるからだろうか。