アルゴリズム(全97問中23問目)

キーが小文字のアルファベット1文字(a, b, …,z のいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファベット順にコードとして割り当てられている。

出典:平成27年秋期 問 5

  • a と i
  • b と r
  • c と l
  • d と x
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
ASCIIコード上で、アルファベットは並び順どおりに連続した位置に配置されています。
05_1.gif
ハッシュ表の大きさが10であり、格納位置を求めるハッシュ関数にASCIIコードを10進表記法で表したときの1の位の数を使うことから、1の位が同じとなるアルファベット同士では、ハッシュ表上の格納位置が同じになってしまうシノニム(衝突)が発生することになります。

つまりASCIIコード上のアルファベットを順番に並べたときの2つの文字の距離が、10の倍数になっているものが衝突が起こるキーの組合せです。
  • a と i の距離は、8のため衝突は発生しません。
  • b と r の距離は、16であるため衝突は発生しません。
  • c と l の距離は、9であるため衝突は発生しません。
  • 正しい。d と x の距離は20で、10の倍数であるため衝突が発生します。
05_2.gif

この問題の出題歴


Pagetop