【Python入門】ハッシュ法の仕組み

　多くのプログラミング言語で用いられているハッシュ法は、集合や辞書といったデータ構造が非常に高速に要素の存在確認や追加・削除を行うための基盤となっています。Pythonの集合（set）は、各要素にハッシュ関数を適用してハッシュ値を計算し、その値に基づいて専用のハッシュテーブル内の適切な領域に格納されます。
　ここでは、リストと集合における要素の管理方法の違いを例に、ハッシュ法の基本的な仕組みと、衝突発生時の対処方法について、具体例と図を用いて分かりやすく解説します。

１．ハッシュ法の基本概念

　ここでは、まずリストと集合で同じ値がどのように格納されるかを比較し、ハッシュ法の基本的な動作を理解します。なお、以下の例では集合に格納する値として、

"orange"（6文字）
"purple"（6文字）
"cyan"（4文字）
"magenta"（7文字）
を用います。

1.1. リストにおける要素の格納方法

　リストは、追加した順番に要素を先頭から末尾まで順次格納します。例えば、次のように値を追加した場合の状態は以下の通りです。

リスト

[0]	[1]	[2]	[3]
orange	purple	cyan	magenta

解説

リストは、値が追加された順序そのままに保持され、インデックス0から始まる連続した番号が割り当てられます。
この構造では、要素の存在確認は先頭から順に比較する線形探索が行われます。

1.2. 集合におけるハッシュ法の利用とハッシュテーブルの仕組み

　集合は、各要素に対してハッシュ関数を適用し、その結果得られるハッシュ値に基づいて、あらかじめ用意された複数の領域（ハッシュテーブル）に格納されます。ここでは、ハッシュテーブルの領域数を8個（0～7）とし、ハッシュ関数を「文字列の長さ」とする簡単な例を示します。

"orange" は6文字 → ハッシュ値 6
"purple" は6文字 → ハッシュ値 6
"cyan" は4文字 → ハッシュ値 4
"magenta" は7文字 → ハッシュ値 7

これをもとに、各値の格納先を決定すると次のような図になります。

ハッシュテーブル（領域番号: 0～7）
-------------------------------------------------
領域0:　
領域1:　
領域2:　
領域3:　
領域4:　
領域5:　
領域6: 'orange', 'purple'
領域7: 'magenta'
-------------------------------------------------
※ "cyan" はハッシュ値 4 なので、領域4に格納される
-------------------------------------------------
領域0:　
領域1:　
領域2:　
領域3:　
領域4: 'cyan'
領域5:　
領域6: 'orange', 'purple'
領域7: 'magenta'
-------------------------------------------------

解説

ハッシュ関数により、各文字列の長さがそのままハッシュ値となり、領域番号として使用されます。
上記の例では、"orange" と "purple" の両方が6文字なので同じ領域6に格納され、"cyan" は領域4、"magenta" は領域7に格納されます。
ハッシュテーブルはリストのように順序ではなく、ハッシュ値に基づいて要素が格納されるため、探索はほぼ定数時間で行われます。

2．ハッシュ法の衝突と対処法

　ハッシュ法では、異なる値が同じハッシュ値を持つ場合（例："orange" と "purple" はどちらも6文字）の「衝突」が発生します。ここでは、衝突が発生した場合の対処法として、主に開番地法と連鎖法について概説します。

2.1. ハッシュの衝突の例（開番地法の場合）

　例えば、すでに領域6に "orange" と "purple" が格納されている状態で、新たに "indigo"（6文字）を追加するとします。

"indigo" は6文字 → ハッシュ値 6 → 本来は領域6
　しかし領域6はすでに使用中のため、開番地法（オープンアドレス法）では別の空いている領域を探します。ここでは、簡単な例として「5個先の領域」を使用し、
6 + 5 = 11 → 11 mod 8 = 3
となり、領域3が空いていればそこに "indigo" を格納します。

初期状態（領域6に "orange" と "purple"、領域4に "cyan"、領域7に "magenta"）:
-------------------------------------------------
領域0:　
領域1:　
領域2:　
領域3:　
領域4: 'cyan'
領域5:　
領域6: 'orange', 'purple'
領域7: 'magenta'
-------------------------------------------------

"indigo" を追加（衝突発生、5個先 → 領域3に格納）:
-------------------------------------------------
領域0:　
領域1:　
領域2:　
領域3: 'indigo'
領域4: 'cyan'
領域5:　
領域6: 'orange', 'purple'
領域7: 'magenta'
-------------------------------------------------

解説

衝突が発生した場合、開番地法では新しい格納先が見つかるまで一定のルールに従って探索を行います。
Python（CPython）ではより複雑な再ハッシュ戦略が用いられていますが、基本的なアイデアは同じです。

2.2. 衝突対処法：連鎖法の場合

　別の対処法として、連鎖法（チェイン法）があります。連鎖法では、同じ領域に複数の値をリンクリストなどで連結して格納します。たとえば、領域6に "orange" と "purple" がすでに格納されている場合、"indigo" も同じ領域に連結して格納します。

連鎖法での格納例（領域6）:
-------------------------------------------------
領域6: → "orange" → "purple" → "indigo"
-------------------------------------------------

解説

連鎖法では、同一領域に複数の値が存在しても、探索時に連結リストをたどることで目的の値を見つけることができます。
ただし、連鎖が長くなると探索時間が増加するため、ハッシュテーブルのサイズやハッシュ関数の選定が重要となります。

まとめ

ハッシュ法は、集合や辞書が高速に要素を管理・検索できる理由の中心にある技術です。

基本概念として、各値にハッシュ関数を適用し、得られたハッシュ値に基づいてハッシュテーブル内の適切な領域に格納します。
リストとの比較では、リストが順序通りに値を格納し線形探索を行うのに対し、集合はハッシュ法によりほぼ定数時間で探索を実現します。
衝突対策として、オープンアドレス法（開番地法）や連鎖法（チェイン法）などの手法が用いられ、さらにセキュリティ向上のために乱数が利用されるなど、実用上の工夫がなされています。

　これらの仕組みを理解することで、Pythonのみならず多くのプログラミング言語におけるデータ構造の実装方法とその性能の秘密を深く理解することができます。