平成22年度 秋期 午前 問7
アルゴリズム
ハッシュ法に関する問題
5けたの数 a₁a₂a₃a₄a₅ を，ハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a₁＋a₂＋a₃＋a₄＋a₅, 13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321 は次の配列のどの位置に入るか。ここで，mod(x, 13) の値は，x を13で割った余りとする。
〔図〕 位置 配列 0 ┌──────┐ 1 ├──────┤ 2 ├──────┤ ⋮ │ ⋮ │ 11 ├──────┤ 12 └──────┘ （位置 0〜12 の13個の枠。⋮ は途中の省略）
- ア1
- イ2
- ウ7
- エ11
答えと解説を見る
✓ これが正解イ2
解説
各けたの和15を13で割った余り2の位置に入ります。
ハッシュ法では、格納したいデータからハッシュ関数で値を1つ計算し、その値に対応する位置に入れます。ここでのハッシュ関数は、5けたの数のけたを1つずつ取り出して足し、その合計を13で割った余りを返すものです。足すのは数そのものではなく、各けたの数字である点に気をつけます。5と4と3と2と1を足すと15になり、15を13で割ると商が1、余りが2です。配列の枠は0から12までの13個で、番号は0から始まりますから、求めた余りの値がそのまま入る位置の番号になります。判定の軸は2つあります。足す対象がけたの数字であることと、割った余りを位置の番号としてそのまま読むことです。
ほかの選択肢はなぜ違うのか
- ア1：けたを足した15を13で割った余りは2なので、この位置は指されません。枠の番号は0から始まっているため、余りの値そのものが位置の番号になります。
- ウ7：5けたの数そのものを13で割った余りにあたる値です。54321を13で割ると商が4178で余りがこの値になりますが、ハッシュ関数が足すのは各けたの数字のほうです。
- エ11：各けたを足してから13で割るという手順からは、この値は出てきません。合計の15でも5けたの数そのものでも、13で割った余りは別の値になります。
この問題の用語
- ハッシュ関数どんな長さのものからも決まった長さの値を作り出す計算。少しでも中身が変われば、できあがる値は大きく変わります。
- ハッシュ値データから計算した固定長の値のこと。同じデータなら必ず同じ値になるので、データの比較や検索を速くするのに使われます。
出典：平成22年度 秋期 基本情報技術者試験 午前 問7（改変：原典の図表をテキストに書き起こした）
同じ用語が出る問題
- 令和7年度 科目A 問9：暗号の危殆化に該当するもの（ハッシュ関数）
- 令和6年度 科目A 問9：ペネトレーションテストの問題（ハッシュ値）
- 令和6年度 科目A 問2：衝突が起こるキーの組合せ（ハッシュ関数）
- 令和元年度 秋期 午前 問36：動的解析に該当するもの（ハッシュ値）
- 平成27年度 秋期 午前 問36：デジタル署名に関する問題（ハッシュ関数）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）