ハッシュ関数の余りから配列位置をどう求めるか
基本情報技術者試験 令和元年度秋期 午前 問10 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
10進法で5桁の数を、ハッシュ法を用いて配列に格納したい。ハッシュ関数をmod(, 13)とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321は配列のどの位置に入るか。ここで、mod(,13)は、を13で割った余りとする。
- ア
1
- イ
2
- ウ
7
- エ
11
会話形式の解説
講師この問題では、指定された計算でハッシュ値を出し、図の位置番号と照らし合わせます。まず何を足しますか。
受験者54321をそのまま使うのではなく、5つの桁に分けて足すのですね。
講師はい。5＋4＋3＋2＋1で、合計はいくつですか。
受験者15です。次は15を13で割りますが、商の1を使うのでしょうか。
講師使うのは余りです。15＝13×1＋2なので、商は1、余りは2です。modで求めるハッシュ値は2になります。
受験者では、位置1は商を選んでしまった答えですね。図ではハッシュ値と同じ番号の位置を見ればよいですか。
講師そのとおりです。ハッシュ値が2なので、54321を格納するのは位置2です。
受験者位置7と位置11も選択肢にありますが、どちらも計算した余りとは違いますね。
講師はい。位置7ならハッシュ値が7、位置11なら11である必要があります。今回の余りは2なので、どちらも選びません。
受験者各桁を足して15を出し、13で割った余りの2を図の位置番号に対応させるのですね。
講師はい。modの問題では、割り算をした後に商ではなく余りを使っているか、最後に確かめましょう。
まとめ
54321の各桁の和は、5＋4＋3＋2＋1＝15です。15を13で割ると、商は1、余りは2になります。ハッシュ関数mod(15，13)の値は余りの2なので、図の位置2に格納します。正解はイです。
解答・解説
正解はイです
この問題のテーマ
各桁の和を使うハッシュ関数で、数値を格納する配列の位置を求める問題です。
解き方の考え方
54321を5つの桁に分けると、5、4、3、2、1です。したがって、各桁の和は5＋4＋3＋2＋1＝15となります。15＝13×1＋2なので、13で割った余りは2です。図ではハッシュ値と同じ番号の位置に格納するため、位置2を選びます。
選択肢ごとの解説
- ×ア 1位置1は、計算で得た余りと一致しません。15を13で割ったときの1は商であり、このハッシュ関数が使う値は余りです。
- ○イ 2位置2は、計算したハッシュ値2と一致します。問題文の格納方法に従うと、54321はこの位置に入ります。
- ×ウ 7位置7に入れるには、ハッシュ値が7である必要があります。各桁の和15を13で割った余りは2なので、7にはなりません。
- ×エ 11位置11も、求めたハッシュ値とは異なります。各桁の和から計算した余りは2なので、位置11は選びません。
POINT
- まず、指定されたとおりに5桁の各数字を足します。
- mod(x，13)で求めるのは、xを13で割った商ではなく余りです。
- 図の位置番号と、計算したハッシュ値を照合します。