修了試験 2022-06-12実施分 基本情報技術者試験 問8

解説

正解は2です。 ハッシュ法は、キーからハッシュ関数で格納位置を計算し、その位置にデータを置く方法です。 この問題のハッシュ関数は、5つの桁の数字を足し合わせ、13で割った余りを位置とします。 【計算】 54321の各桁はa_1＝5、a_2＝4、a_3＝3、a_4＝2、a_5＝1です。 各桁の和は5＋4＋3＋2＋1＝15です。 15を13で割ると、商は1で余りは2です。 したがって、mod(15，13)＝2となり、配列の位置2に格納します。 【選択肢別解説】 1：× 位置1になるのは、各桁の和を13で割った余りが1の場合です。 54321の各桁の和15では余りは2です。 2：○ 各桁の和15を13で割った余りは2なので、位置2に格納されます。 3：× 位置7になるのは、各桁の和を13で割った余りが7の場合です。 54321の各桁の和15を13で割った余りは2なので、位置7にはなりません。 4：× 位置11になるのは、各桁の和を13で割った余りが11の場合です。 各桁の和15の余りは2なので、位置11にはなりません。 【ポイント】 ハッシュ値の計算は、問題文の関数定義（ここでは各桁の和と13の剰余）に忠実に従うことが大切です。 異なるキーが同じ位置になる現象をシノニム（衝突）といい、対策も頻出です。