ハッシュ

連想配列、マップ、ハッシュ、ハッシュテーブル、ハッシュマップ、などなど配列とリストの時と同じく理解が完全ではなさそうなので、アタマの整理。

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

マップ

以下の条件を満たすデータ構造

• 検索キーを元に対応する値を取得可能
• データの追加と削除が高速
• データの検索も高速

マップの実装にはツリーマップとハッシュマップの2通りある。

連想配列

データ構造よりもプログラミング言語の文脈で出てくることが多いか。マップだと思っておけば差し支えないと思われる。

ハッシュマップ

マップの高速な実装。検索キーに対応する数値（※1）を適当に決め（※２）、あらかじめ確保しておいた配列Array（※３）の対応要素(例: ハッシュ値が10ならArray[10])にkey/value構造体へのポインタを格納する。

• ※１ ハッシュ値
• ※２ ハッシュ関数
• ※３ ハッシュテーブル（ハッシュ表）

ハッシュ値の衝突への対応

ハッシュ表サイズをなるべく大きな素数にするなど、衝突を避ける工夫はあるがそれでも衝突は理論上必ず起こるので対策が必要。

チェーン法

衝突した同じハッシュ値を持つ要素（key/value)をリストで連結する。リストが長くなるとリニアサーチになるので、検索に時間が掛かってしまう。

再ハッシュ法

衝突したら別の位置に要素を格納する。

まとめ

マップ／ハッシュについて、ざっとアタマの中を整理してみた。
理解が正しくない点もあると思うので指摘歓迎。