応用情報技術者 2011年 春期 午前2 問08
問題文
キーが小文字のアルファベット1文字(a, b, ...、zのいずれか)であるデータを、大きさが 10のハッシュ表に格納する。ハッシュ関数として、アルファベットの ASCII コードを 10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCII コードでは、昇順に連続した 2進数が、アルファベット順にコードとして割り当てられている。
選択肢
ア：aとi
イ：bとr
ウ：cとl
エ：dとx（正解）
キーが小文字のアルファベット1文字のハッシュ衝突問題【午前2 解説】
要点まとめ
- 結論：ASCIIコードの1の位の数字が同じキー同士が衝突し、正解は「エ: dとx」です。
- 根拠：小文字アルファベットは連続したASCIIコードで、ハッシュ関数は1の位の数字を使うため、1の位が一致すると衝突します。
- 差がつくポイント：ASCIIコードの具体的な値を理解し、1の位の数字を正確に計算できるかが重要です。
正解の理由
小文字アルファベットのASCIIコードは'a'が97、'b'が98、…、'z'が122です。
ハッシュ関数はASCIIコードの1の位の数字を使うため、例えば'a'(97)は7、'i'(105)は5となり衝突しません。
'd'(100)と'x'(120)は共に1の位が0であり、同じハッシュ値になるため衝突します。
したがって、正解はエ: dとxです。
ハッシュ関数はASCIIコードの1の位の数字を使うため、例えば'a'(97)は7、'i'(105)は5となり衝突しません。
'd'(100)と'x'(120)は共に1の位が0であり、同じハッシュ値になるため衝突します。
したがって、正解はエ: dとxです。
よくある誤解
ASCIIコードの十の位や他の桁を見てしまい、1の位だけを使う点を忘れることがあります。
また、アルファベットの順序とASCIIコードの数値が必ずしも直感的に一致しないため混乱しやすいです。
また、アルファベットの順序とASCIIコードの数値が必ずしも直感的に一致しないため混乱しやすいです。
解法ステップ
- 小文字アルファベットのASCIIコードを確認する（例：a=97, b=98, …）。
- 各キーのASCIIコードの1の位の数字を抽出する。
- 同じ1の位の数字を持つキーの組み合わせを探す。
- 衝突が起こる組み合わせを選択肢から特定する。
選択肢別の誤答解説
- ア: a(97→7)とi(105→5)は1の位が異なり衝突しません。
- イ: b(98→8)とr(114→4)も1の位が異なります。
- ウ: c(99→9)とl(108→8)も異なるため衝突しません。
- エ: d(100→0)とx(120→0)は1の位が同じで衝突します。
補足コラム
ハッシュ関数の設計では、衝突を減らすために入力データの特徴をよく理解し、均等に分散する関数を選ぶことが重要です。
ASCIIコードの性質を利用した簡単なハッシュ関数は学習用に適していますが、実務ではより複雑な関数が使われます。
ASCIIコードの性質を利用した簡単なハッシュ関数は学習用に適していますが、実務ではより複雑な関数が使われます。
FAQ
Q: なぜASCIIコードの1の位だけを使うのですか？
A: 問題文で指定されたハッシュ関数が「1の位の数字を使う」と明示されているためです。
A: 問題文で指定されたハッシュ関数が「1の位の数字を使う」と明示されているためです。
Q: 大文字アルファベットでも同じ方法で衝突を調べられますか？
A: はい、大文字もASCIIコードが連続しているため同様に1の位で衝突を調べられますが、コード値は異なります。
A: はい、大文字もASCIIコードが連続しているため同様に1の位で衝突を調べられますが、コード値は異なります。
関連キーワード: ASCIIコード、ハッシュ関数、衝突、小文字アルファベット、ハッシュテーブル
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！