平成23年度 特別 午前 問8

✓ これが正解エd と x

解説

dとxは並び順が20離れていて、1の位がそろいます。

この設問は、英小文字に割り当てられた具体的な値を覚えていなくても解けるように作られています。鍵になるのは最後の一文で、アルファベット順に連続した値が割り当てられていると断ってあります。すると、二つの文字に割り当てられた値の差は、二つの文字がアルファベットの並びの中でどれだけ離れているかと同じになります。ここで、使うハッシュ関数は10進表記の1の位を取るものですから、これは10で割った余りを取ることと同じです。余りが等しくなるのは差が10の倍数になるときですから、確かめるべきものは並び順の差だけに絞れます。先頭の文字の値がいくつであっても、引き算のときに打ち消し合うからです。正解となる組合せでは、aから数えて4番目の文字と24番目の文字が対になっていますので、差は20です。20は10の倍数ですから、二つは同じ位置に入ろうとし、衝突が起こります。英小文字のaに割り当てられた値を97として確かめても、同じ結論になります。4番目の文字は100で1の位が0、24番目の文字は120で1の位も0となり、ハッシュ表の同じ位置を指します。並び順の差だけを見る解き方なら暗算で済みますし、設問が置いた最後の一文は飾りではなく、その解き方を許している条件だと分かります。

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

• アa と i：aから数えて1番目と9番目の組で、離れている数は8です。10の倍数ではないため余りは一致せず、割り当てられた値で見ても7と5になって別の位置に入ります。
• イb と r：2番目と18番目の組で、離れている数は16です。10の倍数まであと4足りず、値で見ても8と4になりますから、同じ位置を争うことはありません。
• ウc と l：3番目と12番目の組で、離れている数は9です。10に近いので紛らわしいのですが、余りは9と8に分かれ、一つずれた位置に収まります。