平成21年春期試験午前問題 問6

自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
 h(x)=x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,n はハッシュ表の大きさであり,x mod n は x を n で割った余りを表す。

  • a+bがnの倍数
  • a-bがnの倍数
  • nがa+bの倍数
  • nがa-bの倍数
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
キーaのハッシュ関数は a mod n,キーbのハッシュ関数は b mod nです。この2つが一致する場合を方程式で表すと

 a mod n=b mod n
 (a mod n)-(b mod n)=0
 (a-b) mod n=0

a-bがnで割りきれるときにこの等式が成り立つことがわかるので、衝突する条件は「a-bがnの倍数」ということになります。

この問題の出題歴


Pagetop