応用情報技術者 2015年 秋期 午前2 問05
問題文
キーが小文字のアルファベット1文字 (a, b, zのいずれか)であるデータを、大きさが 10 のハッシュ表に格納する。ハッシュ関数として、アルファベットのASCIIコードを 10 進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCII コードでは、昇順に連続した 2進数が、アルファベット順にコードとして割り当てられている。
選択肢
ア：aとi
イ：bとr
ウ：cとl
エ：dとx（正解）
キーが小文字のアルファベット1文字のハッシュ衝突問題【午前2 解説】
要点まとめ
- 結論：ハッシュ関数はASCIIコードの1の位を使うため、1の位が同じキー同士で衝突が起こる。
- 根拠：小文字アルファベットはASCIIコードで連続しており、1の位の数字が同じなら同じハッシュ値になる。
- 差がつくポイント：ASCIIコードの具体的な値を正確に把握し、1の位の数字を比較できるかが重要。
正解の理由
ASCIIコードで小文字のアルファベットは'a'が97、'b'が98、…と連続しています。
ハッシュ関数は「ASCIIコードの1の位の数字」を使うため、例えば'a'は97で1の位は7、'i'は105で1の位は5。
選択肢の中で1の位が同じになるのは'd'(100)と'x'(120)で、どちらも1の位が0となり衝突します。
よって正解はエです。
ハッシュ関数は「ASCIIコードの1の位の数字」を使うため、例えば'a'は97で1の位は7、'i'は105で1の位は5。
選択肢の中で1の位が同じになるのは'd'(100)と'x'(120)で、どちらも1の位が0となり衝突します。
よって正解はエです。
よくある誤解
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) → 1の位が異なるため衝突しない。
- エ: d(100→0)とx(120→0) → 1の位が同じ0で衝突するため正解。
補足コラム
ASCIIコードは英数字や記号を数値で表現する標準で、小文字アルファベットは97から122まで連続しています。
ハッシュ関数の設計では、衝突を避けるためにキーの特徴をよく理解し、適切な関数を選ぶことが重要です。
ハッシュ関数の設計では、衝突を避けるためにキーの特徴をよく理解し、適切な関数を選ぶことが重要です。
FAQ
Q: なぜASCIIコードの1の位だけを使うのですか？
A: 問題文で指定されたハッシュ関数の仕様であり、簡単に計算できるためです。
A: 問題文で指定されたハッシュ関数の仕様であり、簡単に計算できるためです。
Q: 衝突が起きるとどうなりますか？
A: 同じハッシュ値に複数のキーが割り当てられ、衝突解決の処理が必要になります。
A: 同じハッシュ値に複数のキーが割り当てられ、衝突解決の処理が必要になります。
関連キーワード: ASCIIコード、ハッシュ関数、衝突、小文字アルファベット、ハッシュテーブル
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！