HOME»プロジェクトマネージャ平成23年特別»午前Ⅰ 問3
プロジェクトマネージャ平成23年特別 午前Ⅰ 問3
問3
キーが小文字のアルファベット1文字（a, b, …， z のいずれか）であるデータを，大きさが10のハッシュ表に格納する。ハッシュ関数として，アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。
- a と i
- b と r
- c と l
- d と x
- [出典]
- 応用情報技術者
平成23年特別 問8と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
エ
解説
ASCIIコード上で、アルファベットは並び順どおりに連続した位置に配置されています。
ハッシュ表の大きさが10であり、格納位置を求めるハッシュ関数にASCII コードを10進表記法で表したときの１の位の数を使うことから、１の位が同じとなるアルファベット同士では、ハッシュ表上の格納位置が同じになってしまうシノニム（衝突）が発生することになります。
つまりASCII コード上のアルファベット同士の距離が、10の倍数であるものが衝突が起こるキーの組合せです。
つまりASCII コード上のアルファベット同士の距離が、10の倍数であるものが衝突が起こるキーの組合せです。
- a と i の距離は、8のため衝突は発生しません。
- b と r の距離は、16であるため衝突は発生しません。
- c と l の距離は、9であるため衝突は発生しません。
- d と x の距離は、20(10の倍数)であるため衝突が発生します。