応用情報技術者試験(AP) 平成２３年秋期試験 問5
応用情報技術者試験(AP) 平成２３年秋期試験一覧
応用情報技術者試験(AP) 平成２３年秋期試験 問5
自然数をキーとするデータを、ハッシュ表を用いて管理する。
キー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のハッシュ関数は 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の倍数」ということになります。
|
Copyright (C) 応用情報技術者試験(AP)～午前過去問題解説ガイド. All Rights Reserved.