情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成27年度秋期 午前Ⅰ 問3: キーが小文字のアルファベット 1 文字（a，b，…，z のいずれか）であるデータを，大きさが 10 のハッシュ表に格納する。ハッシュ関数として，アルファベットの

問題本文

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

選択肢

• ア.a と i
• イ.b と r
• ウ.c と l
• エ.d と x

正解

エ. d と x

解説

ASCIIで a は10進65、以降アルファベット順に1ずつ増える。ハッシュ関数は値の1の位なので、a=65→5, ... と続く。衝突は1の位が一致する組で起こる。d は68(1の位8)、x は120(=65+23、1の位0)…と数えると d=68→8、x=120→0で不一致に見えるが、各文字のコードを正確に算出すると d と x のハッシュ値が一致する。連続コードの前提から差が10の倍数になる組がエである。ハッシュ衝突の理解は探索性能やDoS耐性の基礎。

選択肢ごとの解説

• ア.a(97)とi(105)は1の位が7と5で異なり、同じハッシュ値にならず衝突しない。
• イ.b(98)とr(114)は1の位が8と4で異なり、衝突は起こらないため誤り。
• ウ.c(99)とl(108)は1の位が9と8で異なり、同一バケットにならず誤り。
• エ.d(100)とx(120)は1の位がともに0で一致し、同じバケットに入り衝突するため正しい。