ハッシュ法と衝突の扱い

結論：ハッシュ法は「キーを計算して置き場所を決める」方法

ハッシュ法とは、データのキー（会員番号など、探すときの目印になる値）をハッシュ関数（決まった計算式）に入れ、出てきた値（ハッシュ値）を格納場所（アドレス）として使う方法です。探すときも同じ計算をすれば置き場所がすぐに分かるので、表を端から順に見る必要がありません。

たとえるなら、ロッカーの番号を「誕生日の日にちの数字」で決めるルールです。15日生まれの人は15番のロッカーと決まっているので、名簿をめくらずに一発でたどり着けます。

前回の探索アルゴリズムと比べると、違いがはっきりします。

「ハッシュ法の説明はどれか」で混ぜられる方式

定義を問う問題では、別のアクセス方式や検索技術の説明がひっかけとして並びます。正解の決め手は「関数（アルゴリズム）で変換した値を格納アドレスにする」という言い回しです。

「対応表を使う」と「計算で求める」の違いが最大のポイントです。ハッシュ法は表を引かずに計算するので速く、データが増えても扱いやすい（スケーラビリティが高い）と説明されます。

衝突（シノニム）は必ず起こりうる

違うキーなのに同じハッシュ値になることを衝突（コリジョン）といい、衝突したキー同士をシノニム（同義語）と呼びます。誕生日ロッカーの例なら、1月15日生まれと3月15日生まれは同じ15番になってしまいます。

格納場所の数よりキーの種類のほうがずっと多いのがふつうなので、衝突は避けられません。だから「衝突が発生しない方法である」という選択肢は必ず誤りです。衝突したときの処理方法には、大きく2種類あります。

試験の計算問題で出るのはほぼオープンアドレス法のトレース（順に追いかけること）です。

ハッシュ値の計算：問題の式をそのまま実行するだけ

ハッシュ値の計算問題は、問題文に書かれた変換ルールを1ステップずつ忠実に実行するだけです。知識より「手順を飛ばさない」ことが問われます。

よく出る道具は mod（割り算の余り）です。たとえば mod(15, 13) は「15 を 13 で割った余り」なので 2 です。余りは必ず 0〜(割る数−1) の範囲に収まるため、表の大きさで割れば必ず表の中の番号になります。

ほかに「キーを11進数とみなして10進数に直す」（基数変換法）のような変わったルールも出ますが、やることは同じです。どの桁を使うか・切り捨てるかを問題文のとおりにやれば解けます。

衝突の判定：ASCII コードは「並び順の差」で解く

ASCII コードとは、文字を数値で表す代表的な文字コードです。小文字 a〜z には連続した番号が順に振られていて、a は 10 進で 97 です。

「1の位をハッシュ値にする」なら、1の位が同じになる組が衝突です。番号が連続しているので、アルファベット順で10文字離れた（差が10の倍数）文字同士が衝突します。a=97 を覚えていなくても、この性質だけで解けます。

オープンアドレス法のトレース：表を書いて1件ずつ埋める

トレース問題はメモ用紙に表（アドレスの欄）を書いて、データを1件ずつ順番に入れていくのが確実です。頭の中だけで追うと、途中で埋まった場所を見落とします。

注意点は2つです。1つは「最終アドレスの次は先頭に戻る」というルールがあるかどうか。もう1つは、ずらし方が「+1」だけとは限らず、「+1 がだめなら +4」のように問題ごとに独自のルールがあることです。

flowchart TD
  A["キーからハッシュ値を計算"] --> B{"その場所は空いている？"}
  B -- "はい" --> C["そこに格納"]
  B -- "いいえ（衝突）" --> D["ルールどおり次の候補へ（最後の次は先頭）"]
  D --> B

試験での問われ方

• 定義問題：「関数で格納アドレスを求める」が正解。対応表＝索引、次のアドレスをたどる＝ポインタ、そのままアドレス＝直接アドレス指定、と見分ける。
• 特徴問題：「2分木を使う」「衝突しない」「表の大きさに比例する」はすべて誤り。
• 計算問題：桁の和の mod、基数変換などを問題文どおりに計算する。商と余りの取り違えに注意。
• 衝突判定：ASCII の1の位なら、アルファベットの距離が10の倍数かを見る。
• トレース：表を書いて順に埋める。格納の順番を入れ替えないこと。