基本情報技術者試験過去問 令和6年度（2024年）科目A問2
キーが小文字のアルファベット1文字（a，b，…，zのいずれか）であるデータを，大きさが10のハッシュ表に格納する。ハッシュ関数として，アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。
選択肢
- ア：aとi
- イ：bとr
- ウ：cとl
- エ：dとx
- ア
- イ
- ウ
- エ
正解と解き方・学習ポイント（AI解説）
このハッシュ関数は、キー文字のASCIIコードを10進表記したときの1の位（ASCIIコードを10で割った余り）をハッシュ値として使います。小文字はa=97から1文字ごとに1ずつ増えるため、各選択肢の2文字についてASCIIコードの1の位を求め、同じ値になれば衝突します。「d」は100で1の位が0、「x」は120で1の位が0なので衝突し、正解は「エ」です。
Point
この問題は、ハッシュ関数が指定されたときに、キーからハッシュ値を計算し、同じハッシュ値になる組合せ（衝突）を判定できることを確認することがねらいです。あわせて、ASCIIコードがアルファベット順に連続して割り当てられている性質を使って、個々の文字のASCIIコードを計算できることも問われています。
解くために必要な知識
この問題を解くには、ハッシュ関数が作る値と衝突の条件を理解している必要があります。
用語の整理
| 用語名 | 意味 |
|---|---|
| ハッシュ表 | ハッシュ値によって格納位置を決め、検索を行いやすくした表です。 |
| ハッシュ関数 | キーからハッシュ値を計算する規則です。 |
| 衝突（コリジョン） | 異なるキーが同じハッシュ値になり、同じ格納位置になることです。 |
| ASCIIコード | 文字に番号を割り当てた規格です。小文字アルファベットはアルファベット順に連続した数値が割り当てられます。 |
衝突が起きる条件（この問題の設定）
ハッシュ値の計算
- ハッシュ値 = ASCIIコードを10進表記したときの1の位
衝突の判定
-
2つのキーのハッシュ値が同じなら衝突します。
-
10進表記の1の位が同じとは、2つの数の差が10の倍数であることと同じです。
ASCIIコードを暗記しなくてもよい理由
-
小文字アルファベットはASCIIコードが連続です。
-
そのため、2文字のASCIIコードの差は、文字の並び順の差と一致します。
-
よって、並び順の差が10の倍数かどうかだけで衝突を判断できます。
問題の解法手順
解く手順
1. ハッシュ値の決まり方を確認します
-
ハッシュ表の大きさは10です。
-
ハッシュ関数は、ASCIIコードを10進表記したときの1の位を使います。
-
1の位が同じなら、同じ場所に格納されるため衝突します。
2. ASCIIコードが連続である点を使います
問題文より、小文字アルファベットはASCIIコードがアルファベット順に1ずつ増えます。
このため、2文字のASCIIコードの差は、その文字の並び順の差と同じになります。
3. 各ペアの差を計算し、10の倍数かを確認します
aを1番目とすると、各文字の位置は次のとおりです。
| 文字 | 位置 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
| d | 4 |
| i | 9 |
| l | 12 |
| r | 18 |
| x | 24 |
各ペアの位置の差は次のとおりです。
| 選択肢 | ペア | 差 |
|---|---|---|
| ア | a と i | 9 - 1 = 8 |
| イ | b と r | 18 - 2 = 16 |
| ウ | c と l | 12 - 3 = 9 |
| エ | d と x | 24 - 4 = 20 |
差が10の倍数なら1の位が一致するため衝突します。20は10の倍数なので「エ」が衝突します。
選択肢ごとの解説
- ア：不正解
aのASCIIコードは97で、1の位は7です。iはaから8文字後なので97+8=105で、1の位は5です。1の位が一致しないので衝突しません。よって誤りです。
- イ：不正解
bのASCIIコードは98で、1の位は8です。rはbから16文字後なので98+16=114で、1の位は4です。1の位が一致しないので衝突しません。よって誤りです。
- ウ：不正解
cのASCIIコードは99で、1の位は9です。lはcから9文字後なので99+9=108で、1の位は8です。1の位が一致しないので衝突しません。よって誤りです。
- エ：正解
dはaから3文字後なので97+3=100で、1の位は0です。xはdから20文字後なので100+20=120で、1の位は0です。1の位が一致し、同じハッシュ値（番地）になるため衝突が起こります。よって正解です。
まとめ
このハッシュ関数は、キー文字のASCIIコードを10進表記したときの1の位（ASCIIコードを10で割った余り）をハッシュ値として使います。小文字はa=97から1文字ごとに1ずつ増えるため、各選択肢の2文字についてASCIIコードの1の位を求め、同じ値になれば衝突します。「d」は100で1の位が0、「x」は120で1の位が0なので衝突し、正解は「エ」です。
aのASCIIコードは97で、1の位は7です。iはaから8文字後なので97+8=105で、1の位は5です。1の位が一致しないので衝突しません。よって誤りです。
bのASCIIコードは98で、1の位は8です。rはbから16文字後なので98+16=114で、1の位は4です。1の位が一致しないので衝突しません。よって誤りです。
cのASCIIコードは99で、1の位は9です。lはcから9文字後なので99+9=108で、1の位は8です。1の位が一致しないので衝突しません。よって誤りです。
dはaから3文字後なので97+3=100で、1の位は0です。xはdから20文字後なので100+20=120で、1の位は0です。1の位が一致し、同じハッシュ値（番地）になるため衝突が起こります。よって正解です。