自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ５７１、
１１６８、１５６６である三つのレコードのキー値を入力値としてこのハッシュ
関数を施したところ、全てのハッシュ値が衝突した。この時使用した除数は
幾つか。
ア １９３ イ １９７ ウ １９９ エ ２１１
除数をｘ、剰余をｙ とおくと、以下が成り立つ。
ｘ×Ａ＋ｙ ＝ ５７１ ・・・①
ｘ×Ｂ＋ｙ ＝ １１６８ ・・・②
ｘ×Ｃ＋ｙ ＝ １５６６ ・・・③
②－①より (Ｂ－Ａ）ｘ＝１１６８－５７１ ＝ ５９７ ・・・④
③－①より (Ｃ－Ａ）ｘ＝１５６６－５７１ ＝ ９９５ ・・・⑤
③－②より (Ｃ－Ｂ）ｘ＝１５６６－１１６８ ＝ ３９８ ・・・⑥
④-⑥より (Ｂ－Ａ－Ｃ＋Ｂ)ｘ ＝ １９９
１９９は素数だから ｘ ＝ １９９
すなわち、除数は１９９である。
EXCEL ＶＢＡのご相談なら ファーストマクロ へ
タグ：ハッシュ関数
