技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

問２７

自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571、1168、1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ、全てのハッシュ値が衝突した。この時使用した除数は幾つか。

---

正解

ウ

---

解説

除数を x、剰余を y とおくと、以下が成り立つ。
A×x＋y ＝ 571 　・・・�@
B×x＋y ＝ 1168　・・・�A
C×x＋y ＝ 1566　・・・�B

�A−�@より (B−A)x ＝ 1168−571 ＝ 597　・・・�C
�B−�@より (C−A)x ＝ 1566−571 ＝ 995　・・・�D
�B−�Aより (C−B)x ＝ 1566−1168 ＝ 398　・・・�E

�C−�Eより (B−A−C＋B)x ＝ 199

199は素数だから x ＝ 199。
すなわち、除数は199である。

問２６

目次

問２８

---