過去問.JP

自然数をキーとするデータを，ハッシュ表を用いて管理する。

キーxのハッシュ関数h(x)をh(x) = x mod nとすると，任意のキーaとbが衝突する条件はどれか。

ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。

ハッシュ関数を用いたキーの衝突条件についての理解を求めるものです。

ハッシュ関数h(x) = x mod nを用いると、キーをハッシュテーブルに格納する際に用いられるメモリアドレスが、xをnで割った余り（mod演算の結果）として求められます。

つまり、x mod nが等しいとき、キーは衝突状態にあります。

衝突が発生する条件を具体的に見るために、キーaとbを考えます。

aをnで割った時の商がk、余りがx、bをnで割った時の商がl、余りがxだとすると、次のように表せます。

• a = kn + x
• b = ln + x

この2つの式から、共通の余りxについて解くと以下のようになります。

• - a - kn = b - ln

式を整理すると、次のように変形できます。

• - a - b = n(k - l)

ここで、kとlは整数であるため、(k - l)も整数になります。したがって、a - bはnの倍数であるという条件が、キーが衝突する時の条件とわかります。この論理を元に、aとbが衝突する条件は「a - bがnの倍数」であることが確認できます。