計算問題の解き方・10/20
ハッシュ値の計算と、衝突したときの格納位置の求め方
キー（数・文字・16進数など）を決められたハッシュ関数で格納位置に変換し、そこに入るか、衝突するか、衝突したらどこへずらして入れるかを求めます。複数のキーを順に入れて、ある位置に入っているキーや、最初に衝突するキーを答える形でも出題されます。
公開過去問での出題：本試験系 8 回・免除試験 18 回（観測値）
覚える式
- ハッシュ値（格納位置）＝ キーから作った数 mod n（n で割った余り。0〜n−1 のどれかになる）
- 位置を 1 から数える場合は「余り＋1」を格納位置にします
- 衝突時（次のアドレスに入れる方式）：次の位置 ＝ 今の位置＋1。最後の位置の次は先頭に戻ります
解き方の手順
- 問題文のハッシュ関数をそのまま書き写し、「何を足すか（各桁・各文字の順位）」「何で割るか」「余りに＋1 するか」を確認します。
- キーを、割る前の数に直します。各桁の和、文字の順位の和、11進数や16進数とみなした10進数への変換など、問題の指定どおりに作ります。
- その数を n で割った余りを求め、指定があれば＋1 して格納位置にします。
- キーが複数あるときは、空の配列（表）を書き、与えられた順に 1 個ずつ位置を求めて書き込みます。
- 求めた位置が埋まっていたら衝突です。規則どおりに次の候補（次のアドレス、k+1、k+4 など）を順に調べ、空いた最初の位置に入れます。最後の位置の次は先頭に戻ることを忘れないでください。
- 全部入れ終わったら、問われている位置のキー、またはキーの位置を表から読み取ります。
例題
格納アドレスが 1〜6 の範囲の直接編成ファイルにおいて，次の条件でデータを格納した場合，アドレス 1 に格納されているデータのキー値はどれか。
〔条件〕
(1) キー値が 3，4，8，13，14，18 の順でデータを格納する。
(2) データのキー値を 5 で割った余りに 1 を加えた値を格納アドレスにする。
(3) 格納アドレスに既にデータがある場合には，次のアドレスに格納する。これを格納できるまで繰り返す。最終アドレスの次は先頭とする。
(4) 初期状態では，ファイルは何も格納されていない。
ア 8
イ 13
ウ 14
エ 18
出典：基本情報技術者試験 科目A免除 修了試験 20180610 実施分 問19（解き方は当サイト作成）
解き方と答えを見る
- 格納アドレス ＝ キー mod 5 ＋ 1（アドレスは 1〜6、6 の次は 1）
- 3：3 mod 5 ＝ 3 → 3＋1 ＝ 4 → アドレス4は空き → 4 に格納
- 4：4 mod 5 ＝ 4 → 4＋1 ＝ 5 → 空き → 5 に格納
- 8：8 mod 5 ＝ 3 → 4 → 埋まり → 5 も埋まり → 6 が空き → 6 に格納
- 13：13 mod 5 ＝ 3 → 4 → 埋まり → 5 埋まり → 6 埋まり → 6 の次は先頭の 1 → 空き → 1 に格納
- 14：14 mod 5 ＝ 4 → 5 → 埋まり → 6 埋まり → 1 埋まり → 2 が空き → 2 に格納
- 18：18 mod 5 ＝ 3 → 4 → 4・5・6・1・2 がすべて埋まり → 3 が空き → 3 に格納
- 結果：1＝13、2＝14、3＝18、4＝3、5＝4、6＝8 → アドレス1は 13
答え：13（イ）
ひっかけ
- 余りに＋1 するのを忘れて、余りをそのままアドレスにしてしまう間違いです。例題では 13 mod 5 ＝ 3 を「アドレス3」としてしまうと表がずれます。アドレスが 1 から始まる問題では＋1 が必要か必ず確認してください。
- 衝突したら次へ進むときに、最後の位置の次は先頭に戻ることを忘れる間違いです。例題で 13 を入れるとき、6 で行き止まりと考えると答えが出せなくなります。表の端に「6 の次は 1」とメモしておくと防げます。
- 各桁の和ではなく、キーの数そのものを割ってしまう間違いです。54321 の問題で 54321 mod 13 を計算すると 7（ウ）になり、誤答の選択肢と一致します。ハッシュ関数の中身（a1＋a2＋…）を必ず読んでください。
- 16進数のデータを 10進数と思い込んで割る間違いです。1A を 10進数の 26 に直してから 8 で割るなど、割る前に基数を変換してください。
類題（手順を使って解く）
類題 1
文字を表の順位に置き換えて合計し、mod 27 の値が基準のキーと同じになるものを探す手順（キーを割る前の数に直す部分）が試されます。
アルファベット3文字で構成されるキーがある。次の式によってハッシュ値hを決めるとき，キー“SEP”と衝突するのはどれか。ここで，a mod bは，aをbで割った余りを表す。
h =（キーの各アルファベットの順位の総和）mod 27
| アルファベット | 順位 |
|---|---|
| A | 1 |
| B | 2 |
| C | 3 |
| D | 4 |
| E | 5 |
| F | 6 |
| G | 7 |
| H | 8 |
| I | 9 |
| J | 10 |
| K | 11 |
| L | 12 |
| M | 13 |
| アルファベット | 順位 |
|---|---|
| N | 14 |
| O | 15 |
| P | 16 |
| Q | 17 |
| R | 18 |
| S | 19 |
| T | 20 |
| U | 21 |
| V | 22 |
| W | 23 |
| X | 24 |
| Y | 25 |
| Z | 26 |
出典：基本情報技術者試験 科目A免除 修了試験 20240128 実施分 問6（問題文は IPA の公開問題。答えと解説はリンク先）
類題 2
具体的な数ではなく、2 つのキーの余りが同じになる条件を式で考える問題で、「衝突＝ハッシュ値が一致すること」の意味が試されます。
自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を
h(x) = x mod n
とすると，任意のキー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
出典：基本情報技術者試験 科目A免除 修了試験 20210613 実施分 問8（問題文は IPA の公開問題。答えと解説はリンク先）
類題 3
衝突したときの次の候補が「＋1」と「＋4」の 2 段階になっている規則で、空の配列に順に書き込んでいくトレースが試されます。
次の規則に従って配列の要素 A[0]，A[1]，...，A[9] に正の整数 k を格納する。k として 16，43，73，24，85 を順に格納したとき，85 が格納される場所はどこか。ここで，x mod y は，x を y で割った剰余を返す。また，配列の要素は全て 0 に初期化されている。
〔規則〕
(1) A[k mod 10] = 0 ならば，k を A[k mod 10] に格納する。
(2) (1)で格納できないとき，A[(k+1) mod 10] = 0 ならば，k を A[(k+1) mod 10] に格納する。
(3) (2)で格納できないとき，A[(k+4) mod 10] = 0 ならば，k を A[(k+4) mod 10] に格納する。
出典：基本情報技術者試験 科目A免除 修了試験 20210124 実施分 問9（問題文は IPA の公開問題。答えと解説はリンク先）