平成27年度 秋期 午前 問5

✓ これが正解エd と x

解説

ハッシュ値が並ぶ場所が同じになる二文字を探します。

ハッシュ表の大きさが 10 なので、このハッシュ関数は 10 で割った余り、つまり 1 の位だけを使います。設問は、昇順に連続した値がアルファベット順に割り当てられていると断っているので、小文字の a を 97 と置けば、b は 98、c は 99 と一つずつ増えていきます。あとは、その文字がアルファベットの何番目かに 96 を足せば値が出ます。二つの文字の 1 の位が一致すれば、同じ場所へ入ろうとして衝突します。d は 4 番目なので 100、x は 24 番目なので 120 となり、どちらも 1 の位が 0 でそろいます。別の見方でも同じ判断ができます。1 の位が等しいということは、二つの値の差が 10 の倍数だということなので、アルファベット順の番号の差を見るだけで足ります。起点を取り違えると 1 の位がまとめてずれてしまうため、先に a を 97 と固定しておくことが分かれ目になります。

ほかの選択肢はなぜ違うのか

• アa と i：a は 97 で 1 の位が 7、i は九番目の文字なので 105 となり 1 の位が 5 です。アルファベット順の番号の差も 8 で 10 の倍数から外れているため、二つは別の場所へ入ります。
• イb と r：b は 98 で 1 の位が 8、r は十八番目の文字なので 114 となり 1 の位が 4 です。番号の差は 16 で、10 で割り切れないので同じ場所には入りません。
• ウc と l：c は 99 で 1 の位が 9、l は十二番目の文字なので 108 となり 1 の位が 8 です。番号の差は 9 で 10 との違いが一つしかなく紛らわしいものの、余りは一致しません。