ハッシュ関数による配列格納位置の計算

正解は イ (2)です。 各桁の和は15で、$15\bmod 13=2$となるため、格納位置は2、すなわちイです。 ハッシュ値は各桁の和を13で割った余りです。衝突処理を考える前に、まず指定されたハッシュ関数をそのまま54321へ適用します。 各桁を加えると$5+4+3+2+1=15$となる。 $15\bmod13=2$を求める。 配列の位置2、すなわちイである。 数 各桁の和 13で割った余り(格納位置) 54321 5+4+3+2+1=15 15−13=2 12345(例) 15 2(同じ位置=衝突) 99999(例) 45 45−39=6 各桁の和が同じになる数(12345 など)は同じ位置になり、衝突(シノニム)が起こります。

10進法で5桁の数a1a2a3a4a5a_1a_2a_3a_4a_5をハッシュ法を用いて配列に格納したい。ハッシュ関数をmod⁡(a1+a2+a3+a4+a5,13)\operatorname{mod}(a_1+a_2+a_3+a_4+a_5,13)とし,求めたハッシュ値に対応する位置の配列要素に格納する場合,54321は配列のどの位置に入るか。ここで,mod⁡(x,13)\operatorname{mod}(x,13)は,xxを13で割った余りとする。

位置

配列

0

1

2

・・・

・・・

11

12

出典令和元年度 秋期 基本情報技術者試験 午前 問10
ア
1
イ
2
ウ
7
エ
11