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

No.16

自然数をキーとするデータを,ハッシュ表を用いて管理する。キー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の倍数
  • [この問題の出題歴]
  • 応用情報技術者 H21春期 問6
  • 応用情報技術者 H23秋期 問5
  • 応用情報技術者 H27春期 問5
  • ソフトウェア開発技術者 H16春期 問13
  • ソフトウェア開発技術者 H17秋期 問13
  • ソフトウェア開発技術者 H19秋期 問12

分類

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

正解

解説

キーaのハッシュ関数は a mod n,キーbのハッシュ関数は b mod nです。この二つが一致する場合を方程式で表し、解くと

 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