【ITニュース解説】A Deep Dive Into Python Dictionaries

Pythonの辞書は、その高速性と柔軟性から、プログラミングにおいて非常に重要なデータ構造だ。簡単なデータ保存から複雑な処理まで幅広く使われている。なぜ辞書はキーを指定すると瞬時に値を取り出せるのか、なぜ項目を追加した順序を覚えているのか、そしてたくさんの項目があってもなぜ高速さを保てるのか、その疑問の答えを探っていく。

私たちが普段使っているPythonは、C言語で書かれたCPythonというプログラムで動いている。辞書を作成したり、キーにアクセスしたりするたびに、CPythonのC言語関数が呼び出されているのだ。辞書の高速性の秘密はハッシュテーブルという仕組みにある。これは、キー（例えば「名前」）を受け取ると、特定の計算（ハッシュ関数）によってデータの格納場所を瞬時に割り出す方法だ。これにより、一つずつ探す必要がなくなり、検索が非常に速くなる。

Pythonの辞書は、Python 3.6以降、大きく分けて二つの部分で構成されている。一つは辞書の基本的な情報を持つ「PyDictObject」、もう一つは実際のキーと値のデータを管理する「PyDictKeysObject」だ。この二重構造が、高速性と順序保持の両立を可能にしている。 PyDictObjectは、辞書内の項目数や、PyDictKeysObjectへのポインタなど、比較的小さな情報だけを持つ。また、ma_valuesという特殊な領域があるが、通常は使われず、値はPyDictKeysObject内に格納される「結合テーブル」方式が取られている。しかし、多数のオブジェクトが同じキーを持つ場合（例えば、多くの学生オブジェクトが共通して「name」や「grade」というキーを持つ場合）、メモリを節約するために「分割テーブル」方式が使われることがある。この場合、共通のキー構造は一つだけ持ち、各オブジェクトはそれぞれの値だけを別の配列に持つことで、メモリ使用量を大幅に削減する。 PyDictKeysObjectは、さらに「dk_indices」と「dk_entries」という二つの重要な配列で構成される。 dk_indicesは、実際のハッシュテーブルであり、キーや値を直接保存しない。その代わりに、dk_entries配列内のデータがどこにあるかを示す「インデックス」（整数の番号）だけを格納する。これにより、ハッシュテーブル自体が小さく保たれ、非常に高速な検索が可能になる。 dk_entriesは、実際のキー、そのキーのハッシュ値、そして値のペアをまとめて格納するシンプルな配列だ。新しい項目が辞書に追加されるとき、この配列の末尾に単純に追記される。この仕組みが、辞書が項目を追加した順序を記憶している理由だ。辞書を順番に処理する際も、このdk_entries配列を先頭から順にたどるだけで良い。このように、dk_indicesは高速な検索に、dk_entriesは順序付きのデータ格納に特化している。

Pythonで空の辞書を作成する際、PyDict_NewというC関数が呼び出される。このとき、CPythonは毎回新しいメモリを確保してハッシュテーブルやデータ配列を作ることはしない。代わりに、Py_EMPTY_KEYSという、あらかじめ用意されたグローバルな空のキーオブジェクトを指し示すだけだ。実際のPyDictObjectのシェル（殻）が作られ、そのma_keysポインタがこの共有の空オブジェクトを指す。そのため、空の辞書の作成は非常に安価で高速な操作であり、多くの空の辞書が作られてもメモリを無駄にしない。

辞書からキーを使って値を取り出すときは、_Py_dict_lookup関数が実行される。まず、指定されたキーのハッシュ値を計算し、そのハッシュ値を使ってdk_indices配列の中からデータのインデックスを割り出す。見つかったインデックスが指し示すdk_entries配列の場所から、実際のキーと値を比較して目的のデータかを最終的に確認する。もし複数のキーが同じハッシュ値になる「衝突」が起きた場合、CPythonは独自のアルゴリズム（perturb変数を使った5*j + 1の計算）で次の探索場所を効率的に見つける。この衝突解決の仕組みにより、たとえハッシュ値があまり良くない場合でも、ほとんどのアクセスは1回か2回の探索で目的のキーにたどり着くため、平均的にはO(1)という非常に高速な処理が実現される。

辞書に新しいキーと値のペアを追加したり、既存のキーの値を更新したりするときは、insertdict関数が使われる。まず、追加しようとするキーがすでに辞書内に存在するかどうかを_Py_dict_lookupで確認する。キーが既に存在すれば、その場所の値を更新するだけだ。もし新しいキーであれば、dk_entries配列の末尾に新しいキー、ハッシュ値、値のペアを追加し、その新しい項目のインデックスをdk_indicesの適切な位置に書き込む。ただし、辞書の容量が不足した場合、insertion_resizeという処理が実行され、辞書全体がより大きな新しいハッシュテーブルとデータ配列に再構築される。この再構築はO(n)のコストがかかるが、CPythonは効率的な成長戦略をとっているため、このO(n)の操作が起こる頻度は非常に低く、平均すると項目の挿入もO(1)の高速な操作として機能する。

辞書から項目を削除する際は、delitem_common関数が呼び出される。項目を削除するだけでは、衝突解決のための探索チェーンが途切れてしまい、将来の検索に影響を及ぼす可能性がある。そのため、CPythonは削除された項目のハッシュテーブル上のスロットをDKIX_DUMMY（ダミー）という特別なマークで置き換える。そして、dk_entries配列内の実際のキーと値はNULLに設定され、参照カウントが減少してメモリが解放される。このダミースロットは、一時的に検索のオーバーヘッドをわずかに増やすものの、削除処理自体は他の要素を移動させる必要がないため、平均的にO(1)で完了する。

辞書に存在しないキーでmy_dict['missing_key']のようにアクセスするとKeyErrorが発生するが、my_dict.get('missing_key')を使うとNoneが返るだけだ。この違いは、背後にあるC関数の設計の歴史的経緯に由来する。get()メソッドは、古い内部関数が元になっており、エラーを抑制して単にNULL（PythonではNone）を返すよう設計されていた。一方、[]アクセスは、より現代的な関数によって処理され、NULLが返された場合に明示的にKeyErrorを発生させるようになっている。

Pythonの辞書は、単一のハッシュテーブルではなく、高速な検索のためのコンパクトな整数ハッシュテーブル（dk_indices）と、挿入順序を保持するデータ配列（dk_entries）を組み合わせたハイブリッドなデータ構造である。この洗練された設計により、辞書は平均O(1)の高速なアクセス速度と、Python 3.7以降で保証される挿入順序の両方を実現しているのだ。