トップ過去問一覧応用情報技術者 平成25年・秋 > 問7
問7

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

解説

a-bがnの倍数

ハッシュ表とは,キーとデータを対応させて保存するもので,高速にデータを読むことが出来ます。衝突とは,2つ以上のデータのキーが一致してしまうことです。

 

H(x)においてキーaとbが衝突する状態は,

a mod n = b mod n

となってしまうことです。この式を変形して

(a mod n)-(b mod n)=0

(a - b)mod n = 0

 よって,a-bがnの倍数の時にハッシュ値が衝突します。

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

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