問2 ハッシュ関数で衝突するキー

基本情報​技術者試験 令和6年度 公開問題 科目A、全20問のうちの問2。

出典:令和6年度 基本情報技術者試験 公開問題 科目A 問2

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

  1. アa と i
  2. イb と r
  3. ウc と l
  4. エd と x
答えと解説を開く

正解はエです。

小文字の a の ASCII コードは 1⁠0 進で 9⁠7 です。アルファベット順に 1 ずつ増えるので、b は 9⁠8、c は 9⁠9、d は 1⁠0⁠0、i は 9⁠7+8=1⁠0⁠5、l は 9⁠7+1⁠1=1⁠0⁠8、r は 9⁠7+1⁠7=1⁠1⁠4、x は 9⁠7+2⁠3=1⁠2⁠0 です。1 の位を取ると、a は 7、i は 5、b は 8、r は 4、c は 9、l は 8、d は 0、x は 0 です。1 の位が同じになるのは d と x の組だけです。また、1 の位が同じになるのはコードの差が 1⁠0 の倍数のときです。d と x の差は 1⁠2⁠0−1⁠0⁠0=2⁠0 で 1⁠0 の倍数です。正解はエです。

ほかの選択肢が違う理由

  • アa は 9⁠7 で 7、i は 1⁠0⁠5 で 5 です。格納先が違うので衝突しません。差は 8 で 1⁠0 の倍数ではありません。
  • イb は 9⁠8 で 8、r は 1⁠1⁠4 で 4 です。差は 1⁠6 で、衝突しません。
  • ウc は 9⁠9 で 9、l は 1⁠0⁠8 で 8 です。差は 9 で、衝突しません。

仕組み

ハッシュ表は、キーをハッシュ関数で番号に変え、その番号の場所にデータを入れる表です。違うキーが同じ番号になることを衝突と言い、衝突したキーどうしをシノニムと言います。衝突したら、別の場所に置くなどの手当てが要ります。

a の ASCII コード 9⁠7 (1⁠6 進で 6⁠1) は覚えておくと便利です。A は 6⁠5 (1⁠6 進で 4⁠1) で、大文字と小文字の差は 3⁠2 です。

この問に出る言葉