Pythonの辞書（dict）検索はどう動く？ハッシュテーブルの仕組みを徹底解説

Pythonの辞書はハッシュテーブルで実装されている

Pythonの辞書（dict）は、内部に「ハッシュテーブル」と呼ばれるデータ構造を採用しています。木構造を使った探索（ツリー検索）は一切行われません。そのため、キーの検索は辞書のサイズ（要素数）にほとんど影響されず、常にほぼ一定の時間——いわゆる償却定数時間（Amortized O(1)）——で完了します。要素が100個でも100万個でも、検索速度はほぼ変わりません。

キー検索の具体的な流れ

辞書でキーを引くとき、内部では次のような手順で処理が進みます。

1. キーのハッシュ値を計算する

まず、組み込みの hash() 関数によってキーのハッシュ値が計算されます。文字列・数値・タプルなど、ハッシュ可能（hashable）なオブジェクトであれば何でもキーとして使えます。

2. ハッシュ値から格納位置を特定する

次に、そのハッシュ値をもとに、テーブル内のどのスロットにデータが格納されているかを特定します。これは配列へのインデックスアクセスに近い処理のため、極めて高速です。

3. 衝突（コリジョン）があれば解決アルゴリズムを実行する

異なるキーが偶然同じスロットを指してしまう「衝突」が発生した場合には、衝突解決アルゴリズムが起動します。CPythonではオープンアドレス法が採用されており、目的のエントリが見つかるまで別の候補位置を順番に調べていきます。それでも最終的には、該当する値へ素早くたどり着けます。

トレードオフ：メモリ使用量との関係

この高速性を実現しているのが、辞書が持つ疎（まばら）な構造です。要素数に対して余裕をもった大きさのテーブルを確保することで衝突の頻度を抑え、検索速度を維持しています。その一方で、リストのような密なデータ構造と比べると、消費メモリが多くなるというトレードオフが存在します。「速さと引き換えに空間を犠牲にする」設計だと言えるでしょう。

まとめ

Pythonの辞書検索は、ハッシュテーブルによって支えられています。キーのハッシュ化 → 格納位置の特定 → 必要に応じた衝突解決、というシンプルな流れで、サイズによらずほぼ一定時間のアクセスを実現しています。大量のデータから高速に値を取り出したい場面では、dictが最有力の選択肢になるのはこのためです。