SC情報処理安全確保支援士試験 午前Ⅰ

平成25年度秋期 情報処理安全確保支援士 午前Ⅰ 問2

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

自然数をキーとするデータを,ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) = x mod n とすると,キー a と b が衝突する条件はどれか。ここで,n はハッシュ表の大きさであり,x mod n は x を n で割った余りを表す。

選択肢

  1. ア
    a + b が n の倍数
  2. イ
    a − b が n の倍数
  3. ウ
    n が a + b の倍数
  4. エ
    n が a − b の倍数
解き方のヒントを見る

剰余ハッシュの衝突を具体値で確かめる

衝突とは異なるキーが同じハッシュ値になることです。条件を抽象的に考え込む前に、問題で与えられた関数の定義を正確に読み取り、手元でいくつかのキーを当てはめて得られる値を比べることで、条件の意味を自分で確かめる姿勢が役立ちます。

この問題で問われていること

観点は一つ、「二つのキーのハッシュ値が一致するとはどういう状態か」を自分の言葉で説明できるかです。剰余演算の結果が何によって決まるかを振り返り、キーそのものが違っても値が同じになりうる理由を意識して検討してください。

視点

ハッシュ関数はキーを格納位置などの値に変換する仕組みです。異なるキーが同じ値に変換されることを衝突と呼びます。剰余を使う方式では、割る数と余りの関係を丁寧に扱うことが理解の鍵になります。学習の際は、まず定義を式として読み取ります。次に小さな数で試して結果を観察し、そこから一般的な条件へと考えを広げる手順が有効です。

確認ポイント

  • ハッシュ関数で何を何で割り、どの値を結果として使うのかを正確に読み取れているか
  • 小さな具体例でハッシュ値を求め、一致するか一致しないかを自分で確かめたか
  • 確かめた例から、値が一致する場合に共通する性質を自分の言葉でまとめられるか
正解と解説を見る

正解

イ

解説

h(x) = x mod n で衝突するのは、a と b を n で割った余りが等しいときです。余りが等しければ a − b は n の整数倍になり、逆に a − b が n の倍数であれば余りは一致します。したがって、正解はイです。

理由

a = p×n + r、b = q×n + r(p、q は整数、0 ≦ r < n)のように、a と b を n で割った余りがどちらも r であるとします。このとき a − b = (p − q)×n と表せるため、a − b は n の倍数になります。逆に a − b = k×n(k は整数)であれば、a = b + k×n となるため、a を n で割った余りと b を n で割った余りは等しくなります。したがって、ハッシュ値が等しくなる h(a) = h(b) という衝突の条件は、「a − b が n の倍数であること」と同値になります。たとえば n = 5、a = 11、b = 1 のとき、差 a − b = 10 は 5 の倍数であり、h(11) = h(1) = 1 となって衝突します。

比較

アとウは和 a + b に注目していますが、衝突は余りが等しいかどうかで決まるため、和は判断の基準になりません。たとえば n = 5、a = 1、b = 4 は和が 5 の倍数ですが、h(1) = 1、h(4) = 4 となり衝突しません。またエは差に注目しているものの、倍数関係の主語と目的語が逆です。n = 6、a = 3、b = 1 のように n が a − b = 2 の倍数であっても、余りはそれぞれ 3 と 1 で衝突しません。したがって、差 a − b のほうが n の倍数であるとするイが正しい条件です。

選択肢ア

これは不正解だよ。a+b が n の倍数であっても衝突するとは限らないよ。たとえば n=5、a=1、b=4 の場合、和 a+b=5 は 5 の倍数だけど、h(1)=1、h(4)=4 で格納位置は異なるよ。逆に a=6、b=1 は h(6)=h(1)=1 で衝突するけれど、和 a+b=7 は 5 の倍数ではないよ。注目すべきなのは和ではなく、それぞれの余りが一致するかどうかだよ。

選択肢イ(正解)

これは正解だよ。a=p×n+r、b=q×n+r(0≦r<n)のように余り r が同じであれば、差は a−b=(p−q)×n となり n の倍数になるよ。逆に a−b=k×n であれば、a と b を n で割った余りは等しくなるよ。したがって、h(a)=h(b) となる衝突の必要十分条件は a−b が n の倍数であることだよ。たとえば n=5、a=11、b=1 では差が 10 で、どちらも余りは 1 だよ。

選択肢ウ

これは不正解だよ。差ではなく和を見ているうえに、倍数関係の向きも逆になっているよ。たとえば n=6、a=1、b=2 のとき、n は a+b=3 の倍数になるけれど、h(1)=1、h(2)=2 で衝突しないよ。反対に n=5、a=6、b=1 は余りがともに 1 で衝突するけれど、5 は a+b=7 の倍数ではないよ。したがって、衝突の条件として成り立たないよ。

選択肢エ

これは不正解だよ。差に注目している点は合っているけれど、倍数関係の向きが逆だよ。たとえば n=6、a=3、b=1 のとき、n は a−b=2 の倍数になるけれど、h(3)=3、h(1)=1 で衝突しないよ。反対に n=5、a=11、b=1 は余りがともに 1 で衝突するけれど、5 は a−b=10 の倍数ではないよ。「a−b が n の倍数」とは異なる条件だよ。

学習のポイント

2つの数を割った余りが等しい条件(合同式)を、その差が法 n の倍数になるという関係に言い換える考え方を押さえましょう。

出典:独立行政法人 情報処理推進機構(IPA)平成25年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問2(公式資料:問題冊子(PDF) / 解答例)

関連する過去問一覧

IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針