問題プレビューID: c17bdec2応用情報技術者試験 2015年(平成27年度)秋期 午前

問 5
応用情報技術者試験 2015年(平成27年度)秋期 午前

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

解説

正解は「エ」です。

'a' の ASCII コードは 9797 で,以降はアルファベット順に 11 ずつ増えます。ハッシュ値はこの 1 の位の数なので,'a'〜'z' のハッシュ値は 77,88,99,00,11,22,33,44,55,66,77,… と 10 周期で循環します。すなわち,ASCII コードの差が 1010 の倍数(10 文字違い)である組合せが同じハッシュ値となり,衝突します。

  • エ: 'd' は 100100,'x' は 120120 で,差は 120−100=20120 - 100 = 20(1010 の倍数)です。したがってハッシュ値はいずれも 00 となり,衝突します。
  • ア: 'a' は 9797,'i' は 105105 で,差は 88 であり衝突しません。
  • イ: 'b' は 9898,'r' は 114114 で,差は 1616 であり衝突しません。
  • ウ: 'c' は 9999,'l' は 108108 で,差は 99 であり衝突しません。

よって正解は「エ」です。

関連問題

本文が同じ・似ている問題を表示しています