データベーススペシャリスト 平成21年春期 午前T 問3

午前T 問3

自然数をキーとするデータを,ハッシュ表を用いて管理する。キー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の倍数
  • [この問題の出題歴]
  • 応用情報技術者
    平成21年春期 問6と同題

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

キー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の倍数」ということになります。
© 2016-2019 データベーススペシャリストドットコム All Rights Reserved.

Pagetop