基本情報技術者 2024年 科目A 問02
問題文
キーが小文字のアルファベット1文字（a, b, …, zのいずれか）であるデータを、大きさが10のハッシュ表に格納する。ハッシュ関数として、アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは、昇順に連続した2進数が、アルファベット順にコードとして割り当てられている。
選択肢
ア：aとi
イ：bとr
ウ：cとl
エ：dとx（正解）
🔒 解説は解答すると表示されます
ハッシュ衝突の判定【午前解説】
正解の理由
ハッシュ関数は「英字の ASCII コードの10進表記での1の位」を使っており、これは数値で言うところの「ASCIIコードを10で割った余り（mod 10）」です。小文字英字は ASCII で連続して割り当てられているため、衝突は ASCIIコードの差が10の倍数になると起きます。
選択肢のうち、エの d と x はそれぞれ ASCII が と であり、1の位はどちらも なので衝突します。よって エ が正解です。
選択肢のうち、エの d と x はそれぞれ ASCII が と であり、1の位はどちらも なので衝突します。よって エ が正解です。
解法ステップ
- 文字の ASCII コードを調べる（小文字は 'a' = から連続）。
- その ASCII コードの1の位（すなわち ）を求める。
- 2つの文字の値が等しければ衝突、異なれば非衝突。
具体例（主要文字のみ）：
- 'a' = → 1の位
- 'b' = → 1の位
- 'c' = → 1の位
- 'd' = → 1の位
- 'i' = → 1の位
- 'l' = → 1の位
- 'r' = → 1の位
- 'x' = → 1の位
上記より、'd' と 'x' は同じ1の位 で衝突します。
（補助としての計算例）
for ch in ['a','i','b','r','c','l','d','x']:
print(ch, ord(ch), ord(ch) % 10)
選択肢別の誤答解説
- ア: a と i
- 'a' は 、'i' は 。1の位が異なるため衝突しません。
- イ: b と r
- 'b' は 、'r' は 。異なるので衝突しません。
- ウ: c と l
- 'c' は 、'l' は 。異なるので衝突しません。
- エ: d と x
- 'd' は 、'x' は 。同じ1の位で衝突します（正答）。
よくある誤解
- ASCIIコードを文字の順序番号（a=1など）だけで考えてしまい、末尾の0〜9の繰り返しという観点を見落とす。
- 「文字が離れていると衝突しない」と誤信するが、差が10の倍数であれば離れていても衝突する（例：d と x は差20で衝突する）。
- ASCII の十進数表記の「1の位」を見落として、16進（0x64など）で考えてしまう。問題は10進の1の位が基準。
補足コラム
小文字英字については ASCII が連続して割り当てられているため、一般に文字 ch のハッシュ値は
と書けます（pos は 'a' を0とする位置）。したがって位置差が10の倍数であれば必ず衝突します。ハッシュ関数の評価では、このような単純な下位桁だけを使う方式は偏り（ある桁に衝突が集中する）を招くことがあり、実際の設計ではより均等化する工夫（乗算法や良好な分散を持つ関数）が必要です。
FAQ
Q: 「1の位」を使うことは同じく「10で割った余り」と考えていいですか？
A: はい。1の位は十進での剰余（mod 10）と同値です。
A: はい。1の位は十進での剰余（mod 10）と同値です。
Q: 大文字と小文字で ASCII はどう違いますか？
A: 大文字は 'A' = から、小文字は 'a' = からで互いに別のコード域です。問題文が小文字に限定しているため上記の連続性が使えます。
A: 大文字は 'A' = から、小文字は 'a' = からで互いに別のコード域です。問題文が小文字に限定しているため上記の連続性が使えます。
Q: 他のハッシュ表サイズ（例えば7や16）の場合はどう判断しますか？
A: ハッシュ表サイズが の場合は ASCII を で割った余りを見ることになります（mod m）。表のサイズに応じた剰余を計算してください。
A: ハッシュ表サイズが の場合は ASCII を で割った余りを見ることになります（mod m）。表のサイズに応じた剰余を計算してください。
関連キーワード: ハッシュ関数、衝突、ASCIIコード、剰余演算、単純ハッシュ
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！