平成23年特別試験問題 午前Ⅰ 問3

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

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

つまりASCII コード上のアルファベット同士の距離が、10の倍数であるものが衝突が起こるキーの組合せです。
  • a と i の距離は、8のため衝突は発生しません。
  • b と r の距離は、16であるため衝突は発生しません。
  • c と l の距離は、9であるため衝突は発生しません。
  • d と x の距離は、20(10の倍数)であるため衝突が発生します。
am1/08_2.gif

Pagetop