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