9月3日、Daniel Lemireが「Python sets and dictionaries can have quadratic-time performance」と題した記事を公開した。PythonのsetとdictがO(1)という常識に反して、二乗時間（O(n²)）や非定数時間の挙動を示す具体的なケースを実測データとともに示したものだ。
「dictの挿入・検索はO(1)」——Pythonエンジニアならほぼ全員がこの前提でコードを書いている。ハッシュテーブルはそういうものだ、と。しかしLemireは、開発者のValentin Ignatevがポストした内容をきっかけに、この常識を実験で崩してみせた。崩し方は2通りある。1つ目はハッシュ衝突によるもの、2つ目はCPUキャッシュによるものだ。AIや機械学習のワークロードで数十万・数百万件規模の辞書を扱う機会が増えた今、この問題は決して他人事ではない。
ハッシュ衝突でO(n²)に化ける
ハッシュテーブルが高速なのは「衝突（collision）が少ない」という前提があってこそだ。衝突とは、異なる2つのオブジェクトが同じハッシュバケットに割り当てられることを指す。衝突が多発すると、本来O(1)のはずの操作が線形探索に近づいていく。
Lemireが使ったのは以下のコードだ：
M = (1 << 61) - 1
values = [i * M for i in range(1, n + 1)]
s = set(values) # insertions
count = sum(v in s for v in values) # checks
(1 << 61) - 1はメルセンヌ素数（2⁶¹−1）だ。Pythonの整数のハッシュ関数はこのメルセンヌ素数をモジュラスとして利用しているため、この値の倍数を並べると大量のハッシュ衝突が意図的に発生する。Apple M4 Max、Python 3.14での計測結果は以下の通りだ：
| n | 時間 |
|---|---|
| 1,000 | 4.8 ms |
| 2,000 | 15.5 ms |
| 4,000 | 65.5 ms |
| 8,000 | 257 ms |
| 16,000 | 1,072 ms |
nが2倍になるたびに時間が約4倍に増えている。これは教科書的な二乗時間（O(n²)）の挙動だ。100,000要素のセット構築には45秒かかったという。メンバーシップチェック（in演算子）も同様で、n=16,000で1,066msを記録した。
衝突を起こせるのは整数だけではない。カスタムクラスで__hash__を実装しているオブジェクトや、ハッシュ値の分布が偏るオブジェクトを大量に格納する場面では、同様の問題が発生しうる。
衝突がなくても「O(1)」にはならない
衝突問題は回避できたとして、それでもdictは本当にO(1)なのか。Lemireはもう一つの実験でそれを否定する。
100万件のランダムな16文字の文字列をキー、整数を値とする辞書を構築し、全キーをシャッフルした順でルックアップする。比較対象として選んだのがfastconstmapだ。fastconstmapは事前にキーが確定している場合に特化した不変マップで、キー・バリューをより密なメモリレイアウトで格納することで、標準dictより大幅にメモリを節約する設計になっている。標準dictの限界を際立たせるための比較対象として、意図的に選ばれている。
Lemireはdictに有利な条件を意図的に設定した。同一の文字列オブジェクトを再利用することで、Pythonの文字列がハッシュ値をキャッシュする仕組みを活かし、dictのハッシュ計算コストをゼロにした。一方のfastconstmapは毎回ハッシュを計算する。それでも結果は以下のようになった（1キーあたりのナノ秒）：
| n | dict | fastconstmap (get_many_into) |
|---|---|---|
| 1,000 | 21.8 ns | 4.3 ns |
| 10,000 | 31.9 ns | 4.8 ns |
| 100,000 | 48.1 ns | 5.2 ns |
| 1,000,000 | 201.9 ns | 11.8 ns |
dictは1,000件で22ns、100万件で202nsと約9倍に悪化している。しかもその増加は対数的で、nが10倍になるたびに一定幅ずつ遅くなっている——これはO(1)ではなくO(log n)に近い挙動だ。アルゴリズムが変わったわけでも、衝突が増えたわけでもない。原因はCPUキャッシュのミスだ。
dictは1キーあたり約116バイトを消費する（文字列オブジェクト、整数オブジェクト等のPythonオブジェクトのオーバーヘッドを含む）。100万件になるとデータ全体がL3キャッシュに収まらなくなり、低速なRAMへのアクセスが多発する。一方fastconstmapは1キーあたり9バイトで済むため、より大きなサイズまでキャッシュに留まり続ける。これはPythonに限らず、JavaのHashMapやC++のstd::unordered_mapでも同様に起きる現象だ。
「O(1)はモデルにすぎない」
Lemireの結論は明快だ。
ハッシュテーブルがO(1)あるいは定数時間だというのはモデルだ。多くの場合に当てはまるかもしれないが、現実ではない。
ハッシュテーブルが本当の意味で定数時間になることはない。データ構造が小さければCPUキャッシュに乗って高速だが、メガバイト級になればRAMへ、さらに大きくなればディスクへとアクセスが移る。メモリ階層が存在する以上、サイズが増えれば遅くなる。計算量のO記法はメモリアクセスコストを抽象化したモデルであり、現実のハードウェア上では必ずしも成り立たない。
「辞書はO(1)だから問題ない」という前提のまま設計を進め、データ規模が数十万・数百万件に達したときに初めて性能劣化に直面する——これはプロダクションでも起きうるシナリオだ。キーの分布を把握し、データ規模に応じた構造を選ぶという判断が、パフォーマンスチューニングの第一歩になる。
実験コードはGitHubで公開されている。
詳細はPython sets and dictionaries can have quadratic-time performanceを参照していただきたい。
