トップ過去問一覧応用情報技術者 平成21年・春 > 問6
問6

自然数をキーとするデータを、ハッシュ表を用いて管理する。
キー 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 の倍数

解説

ハッシュ関数をみると n で割った余りを使っていることがわかります。つまりハッシュ関数は多くても n 通りしかないので衝突が起こる可能性は高いです。また n の倍数( + x )はすべて同じ余り( + x )、つまり同じハッシュなります。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。