アルゴリズム (全82問中53問目)

No.53

自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
 h(x)=x mod n
とする。ここで,n はハッシュ表の大きさであり,x mod n は x を n で割った余りを表す。
 キーaとbが衝突する条件はどれか。
  • a+bがnの倍数
  • a−bがnの倍数
  • nがa+bの倍数
  • nがa−bの倍数
  • [この問題の出題歴]
  • 応用情報技術者 H21春期 問6
  • 応用情報技術者 H23秋期 問5
  • 応用情報技術者 H25秋期 問7
  • 応用情報技術者 H27春期 問5
  • ソフトウェア開発技術者 H16春期 問13
  • ソフトウェア開発技術者 H17秋期 問13

分類

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

正解

解説

キー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の倍数」ということになります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop