テクノロジ系
春期
応用情報技術者 2009年 春期 問6
6 / 80
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x)=x mod n とすると，キーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
正解と解説
表示する
正解 イ
a-bがnの倍数
ハッシュ関数h(x)=x mod n では、キーaとbが衝突するのは a mod n＝b mod n、すなわちaとbをnで割った余りが等しいときです。これは差a−bがnの倍数であることと同値なので選択肢イが正解です。