ハッシュ法の可視化 — チェイン法で衝突を体感

ハッシュ法とは — 場所を「計算」で決める

配列から目的の値を探すとき、先頭から順に見ていくと時間がかかります。ハッシュ法は発想が違います。キーそのものから「何番目に入れるか」を計算してしまい、その場所に直接置く。探すときも同じ計算をすれば一発でたどり着けます。この「場所を計算する関数」がハッシュ関数で、ここでは キー mod 7（7で割った余り、0〜6）を使っています。うまくいけば、挿入も探索も平均 O(1)という一定の速さになります。

衝突（シノニム）は避けられない

ハッシュ関数は「たくさんのキー」を「少ない数のインデックス」に押し込めるので、別々のキーが同じインデックスになることが起きます。これを衝突（コリジョン）、同じ値になったキー同士をシノニム（synonym）と呼びます。たとえば 10 mod 7 も 17 mod 7 も 24 mod 7 もすべて 3。3人が同じ部屋番号を割り当てられる状態です。キーの数が入れ物より多ければ、衝突は原理的に必ず起きます。

衝突の解決：チェイン法とオープンアドレス法

衝突をどうさばくかに、大きく2つの方法があります。

・チェイン法（連鎖法）：同じインデックスに来たキーを、連結リストでつないでぶら下げる。この可視化の方式です。
・オープンアドレス法：ぶつかったら、空いている別のマスを探してそこに入れる（すぐ隣を順に見る「線形探査」など）。

チェイン法は実装がわかりやすく、たくさん入れても破綻しにくいのが利点。探索は「インデックスを計算 → そのバケツの鎖を順にたどる」という流れになります。上の可視化で、同じ行（インデックス）に箱が横につながっていく様子がチェイン法です。

つまずきやすいポイント

偏ると O(1) が崩れて最悪 O(n)。 ハッシュ法が速いのは、キーが各インデックスにばらけているときだけです。もしハッシュ関数が悪くて全部同じ場所に集まると、1本の長い鎖になり、探索は連結リストと同じく先頭からたどることに——つまり O(n) まで落ちます。だから「よく散らばるハッシュ関数」を選ぶことが決定的に重要です。

入れすぎると遅くなる（負荷率）。 「入っている要素数 ÷ 表のサイズ」を負荷率といい、これが高いほど鎖が長くなって遅くなります。実用的なハッシュ表は、負荷率が上がると表を大きく作り直して（リハッシュして）速さを保ちます。

表のサイズは素数が好まれる。 mod で位置を決める場合、表のサイズが素数だと余りが偏りにくく、衝突を減らせます。この可視化で 7 を使っているのもそのためです（10などの丸い数だと、下1桁が同じキーが同じ場所に固まりやすい）。

基本情報技術者試験ではこう出る

「ハッシュ法の平均計算量（→O(1)）」「衝突・シノニムとは何か」「衝突を解決するチェイン法とオープンアドレス法の違い」「mod によるハッシュ値の計算」が定番です。場所を計算で決めるから平均O(1)・衝突は避けられない・偏るとO(n)の3点を、上の可視化で手を動かして押さえておきましょう。関連：データ構造 ／ 探索アルゴリズム ／ 可視化一覧。

📖 記事で深掘り：スタック・キュー・木構造をやさしく図解 ／ 計算量とO記法