ときどき更新されます

CS 周りのお勉強のログ

ダブルハッシュを用いたオープンアドレス法についてメモ

概要

プロコンのためのアルゴリズムとデータ構造を読んでいて，ダブルハッシュを用いたオープンアドレス法のところで， 2つ目のハッシュ関数と配列のサイズと関係のところが最初理解できず， 互いに素の性質から復習したのでメモ

疑問に思ったところ

  • 互いに素でないと生成できない添え字ができるのはなぜか
  • 逆に互いに素ならなぜすべての添え字を作れるのか

理解したことをメモ

基本的には下の記事を見て，互いに素の性質を復習すれば，すべての添え字を作れることについては理解できた． https://hibiyastudy.hatenablog.com/entry/math/naturalnumbers/02#-pq%E3%81%8C%E4%BA%92%E3%81%84%E3%81%AB%E7%B4%A0%E3%81%AA%E3%81%A8%E3%81%8Dp2p3pq-1p%E3%82%92%E3%81%9D%E3%82%8C%E3%81%9E%E3%82%8Cq%E3%81%A7%E5%89%B2%E3%81%A3%E3%81%9F%E4%BD%99%E3%82%8A%E3%81%AF%E7%95%B0%E3%81%AA%E3%82%8B

上の解説を今回のものにあてはめると

ダブルハッシュを用いたオープンアドレス法では，以下の式でハッシュを計算．

\begin{align} (h_1(k) + i \times h_2(k)) \ \textrm{mod} \ m \end{align}

h_2(k) と m が互いに素のとき，すべての添え字 (0 \sim m-1) を表せることの証明

上の記事の③と④を使って考える．

(h_1(k) + h_2(k)) \textrm{mod} \ m, (h_1(k) + 2h_2(k)) \textrm{mod} \ m, \ldots とあるなかで，どこかで同じ値（つまり，添え字）が出てきたとする．
例えば，(1) h_1(k) + ah_2(k) と (2) h_1(k) + bh_2(k) の m で割ったときの余りが同じであったとする．
そして，それぞれの商を x_1, x_2 とし，同じ値である余りを y とする．

このとき，(1) と (2) の差は以下のように表せる．

\begin{align} h_1(k) + ah_2(k) - (h_1(k) + bh_2(k)) &= (a - b)h_2(k) \\ &=(x_1m + y - (x_2m + y)) \\ &=(x_1 - x_2)m \end{align}

つまり，(1) と (2) の差 (a - b)h_2(k) は， m の倍数となる．
この際， h_2(k) と m は互いに素なので，2つの差が m の倍数になるには， (a - b) が m の倍数である必要がある．（詳しくは記事の③）
しかしながら， (a - b) は (0 ～ m - 1) であり， m の倍数になり得ず，矛盾が生じることになる．

上で，互いに素であればすべての添え字を作れることがわかり，互いに素でないと上が成り立たないので，同じ添え字になることがあるのかなというくらいの理解になった．