テクノロジ系
秋期
応用情報技術者 2013年 秋期 問7
7 / 80
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー*のハッシュ関 数h(x)を h(*)=x mod n とすると、キーαと6が衝突する条件はどれか。ここで,nはハッシュ表の大きさで あり、*modnはょをれで割った余りを表す。
正解と解説
表示する
正解 イ
a-bがれの倍数
ハッシュ関数h(x)=x mod nでは、aとbが同じ余りをもつとき衝突する。x mod nが等しい条件は(a-b)がnの倍数であること。a+bがnの倍数などは余り一致の条件にならないため、衝突条件はa-bがnの倍数である。