【はっしゅてーぶる】
ハッシュテーブル とは？
最終更新:
💡 キーから「探す棚」を計算するデータ構造
キーからハッシュ値を計算し、キーと値の組を探す場所を決めるデータ構造。衝突への対処と容量管理などの条件が整うと、検索などを平均的に少ない操作で行える。
📌 このページのポイント
ひよこ 何が速いの？
ペンギン先生 キーから棚の番号を計算して、探す候補を絞れるよ。全部を先頭から探す方法と違い、キーがうまく分散して容量も管理されていれば、平均的に少ない操作で見つけられる。100万件でも実時間が全く同じ、という保証ではないんだ。
ひよこ Pythonのdictもハッシュテーブルなの？
ペンギン先生 CPythonのdictは、サイズを調整するハッシュテーブルで実装されているよ。JavaScriptのMapもキーと値を扱うけど、仕様はハッシュテーブルだけを必須にはしていない。似た使い方ができることと、内部実装が同じことは別なんだ。
ひよこ 衝突って何？
ペンギン先生 違うキーから同じ棚番号が出ることだよ。同じ棚に候補をつなぐチェイニングや、別の空き場所を探すオープンアドレス法などで扱う。棚番号だけで決めず、探しているキーとの一致も確かめるんだ。
ひよこ 順序は保存されないの？
ペンギン先生 ハッシュで場所を決めるだけでは順序は決まらないけど、順序を保持する実装もあるよ。Pythonのdictは3.7以降、挿入順を保持する保証がある。挿入順のためだけに必ずOrderedDictへ変更する必要はないんだ。
ひよこ 衝突が増えたらどうなる？
ペンギン先生 候補の比較や空き場所の探索が増えるよ。単純なチェイニングで全キーが一つの棚に集まれば、探す操作は最大で件数に比例する。キーの分散や表の容量を管理し、平均O(1)を無条件の保証と考えないことが大切だね。
もっと詳しく知りたい人へ
同じハッシュ値なら、同じキーと扱ってよい？
扱えない。異なるキーが同じハッシュ値や格納位置になることがあるため、候補のキーが等しいかも比較する。ハッシュ値は探す場所を絞る手がかりで、キーの一致を保証する識別番号ではない。
まとめ：ざっくりこれだけ覚えればOK！
「ハッシュテーブル」って出てきたら「キーから探す場所を計算する、キーと値のデータ構造」と思えばだいたいOK！
📖 おまけ：英語の意味
「Hash Table」 ＝ ハッシュ表
💬 キーをハッシュ関数で変換し、値を探す場所を決める表だよ