アルゴリズム (全82問中31問目)

No.31

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

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

ASCIIコード上で、アルファベットは並び順どおりに連続した位置に配置されています。
08_1.gif/image-size:406×307
ハッシュ表の大きさが10であり、格納位置を求めるハッシュ関数にASCII コードを10進表記法で表したときの1の位の数を使うことから、1の位が同じとなるアルファベット同士では、ハッシュ表上の格納位置が同じになってしまうシノニム(衝突)が発生することになります。

つまりASCII コード上のアルファベット同士の距離が、10の倍数であるものが衝突が起こるキーの組合せです。
  • a と i の距離は、8のため衝突は発生しません。
  • b と r の距離は、16であるため衝突は発生しません。
  • c と l の距離は、9であるため衝突は発生しません。
  • d と x の距離は、20(10の倍数)であるため衝突が発生します。
08_2.gif/image-size:361×128
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop