- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
本コース1本目で「O記法は増え方の上界であって速さではない」を、2本目で「計算量は前提つきで書かれている」を見ました。今回は最も条件を落とされやすい「ハッシュ表は O(1)」に、規格の逐語を当てます。
まず結論
「ハッシュ表は O(1)」は規格の書き方と食い違っています。C++ 標準ドラフトは `The worst-case complexity for most operations is linear, but the average case is much faster.`。最悪は線形です。
平均 O(1) は「鍵がバケットによく散らばる」という仮定の上に立ちます。Java の javadoc は `assuming` を付けてそう書いています。仮定が崩れれば同じデータ構造が線形に劣化します。
C++ の標準規格は、ハッシュ表(unordered_map など)の操作の計算量をどう書いているでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
規格そのものが「最悪は線形」と書いている
ハッシュ表は鍵からハッシュ値を計算し、その値でバケットという置き場所を決めます。探すときも同じ計算をするので、要素数が増えても置き場所を1回で当てられる——これが「O(1)」の理由です。
ところが C++ 標準ドラフト [unord.req.general] パラグラフ1は、この構造をこう書き出します。
Unordered associative containers provide an ability for fast retrieval of data based on keys. The worst-case complexity for most operations is linear, but the average case is much faster.
最悪は線形(linear)。 規格は同じ操作について最悪と平均を別々に述べています。通説の「ハッシュは O(1)」は嘘ではなく、この文の後半だけを取り出したものです。
なぜ最悪が線形になるのか。バケットの数より鍵の種類のほうが多いからです。入れ物が有限で入れるものが無限なら、どこかは必ず重なります。これが衝突です。規格も衝突を前提に定義を書いています。
Keys with the same hash code appear in the same bucket.
衝突は例外的な事故ではなく、設計に織り込まれた前提です。 全部が1つのバケットに集まれば、その中を順に見ることになります。
公式は「仮定つき」で O(1) と書いている
では平均 O(1) は何を仮定しているのか。Java SE 21 の HashMap javadoc が一文で書いています。
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
assuming the hash function disperses the elements properly among the buckets。 ハッシュ関数が要素をバケットに適切に分散させることを仮定して、という条件付きです。
CPython の実装は同じことを確率の言葉で書いています。Objects/dictobject.c(3.12)の冒頭コメントです。
If we usually find the key we're looking for on the first try (and, it turns out, we usually do -- the table load factor is kept under 2/3, so the odds are solidly in our favor), then it makes best sense to keep the initial index computation dirt cheap.
usually(たいてい)、the odds are solidly in our favor(分がいい)。実装者自身が「必ず」ではなく「たいてい」と書いています。
操作 Average Case Amortized Worst Casek in d O(1) O(n)Get Item O(1) O(n)Set Item O(1) O(n)Delete Item O(1) O(n)
同ページの前文は、その平均が何を仮定しているかも書いています。
The Average Case times listed for dict objects assume that the hash function for the objects is sufficiently robust to make collisions uncommon.
平均と最悪が同じ表に並び、平均の側に仮定が添えられている。 3つの処理系が、それぞれの書き方で同じことを言っています。
Java の HashMap の javadoc が constant-time を宣言している文には、条件節が付いています。その条件とは何ですか。
仮定が崩れたときに何が起きるか、と、崩さないための仕組み
仮定が崩れるとはどういう状態か。Java の javadoc が性質として書いています。
Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table.
any hash table — 特定の実装の弱点ではなく構造そのものの性質です。javadoc は緩和策も併記しますが、To ameliorate impact(和らげる)であって無くすとは書きません。
一方、仮定を崩さないための仕組みが負荷率です。C++ 規格はこう定めます。
The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound.
バケットあたりの平均要素数が上限を下回るよう、バケット数が自動的に増やされる。この作り直しがリハッシュです。
- ・負荷率の上限値は処理系ごとに違う(Java 既定 .75 / CPython 3.12 は 2/3 / C++ 規格は構築時 1.0)
- ・リハッシュは仮定を保つための費用であって、無料ではない
リハッシュ1回は、通常の挿入の18535倍だった
Apple Silicon 上の Docker で Python 3.12.14(Linux 6.10.14 aarch64)、dict への挿入で作り直しを数え(5-1 は10万件)、各回を time.perf_counter_ns() で記録しました(5-2 は20万件)。
== 5-1. dict に 100000 件入れたときの作り直し回数 ==作り直し回数 = 16起きた添字(最初の10): [0, 5, 10, 21, 42, 85, 170, 341, 682, 1365]起きた添字(最後の3): [21845, 43690, 87381]後半の連続する位置の比: ['2.00', '2.00', '2.00']== 5-2. 個々の挿入時間: リハッシュの回だけ高い ==通常の挿入: 199983 回 / 中央値 83 nsリハッシュ: 17 回 / 最大 1538417 ns最大の山は通常の中央値の約 18535 倍リハッシュが起きた回の割合: 0.0085 %
リハッシュ1回は通常の挿入の約18535倍(約1.5ミリ秒。他は83ナノ秒)。しかし起きるのは全挿入の 0.0085% だけです(20万件で17回。10万件なら16回)。起きる位置は 5, 10, 21, 42, 85... と倍々に離れます(後半の比は 2.00)。だから合計を回数で割ると安くなります。
ここで語を区別しておきます。「平均 O(1)」と「1回ごとに O(1)」は違う主張です。 合計を回数で割って安いことは、どの1回も安いことを意味しません。応答時間の上限が決まっている場面では、この稀な山が問題になります。合計で割った安さを指す語は**ならし(amortized)**で、入力の分布を仮定する平均とは別の語です。本コース後半で扱います。
負荷率の上限について、Java・CPython・C++ 規格の3つを並べると何が分かりますか。
鍵がよく散らばる場合
自作クラスの `__hash__` に `hash(self.v)` を返させ、set で最後の要素を探した実測です。n を32倍にしてもほぼ動きません。
n 散らばる側(ns)100 88800 1063200 106
全部が同じバケットに入る場合
同じクラスの `__hash__` だけを定数 0 に変え、同じ探索をした実測です。時間は n にほぼ比例して増えます。
n 全衝突(ns) 前nからの倍率100 4183 -800 35630 8.5x(n は8倍)3200 146979 4.1x(n は4倍)
同じ Python、同じ set、同じ in 判定、同じ要素数です。違うのは鍵の `__hash__` が値を返すか定数 0 を返すかだけ。2つの表から何が読み取れるでしょうか。
それぞれの表で「n を増やしたとき時間がどう増えるか」を見てください。速さそのものではなく、増え方です。
この章のまとめ
- 規格が
The worst-case complexity for most operations is linear, but the average case is much faster.と書いている。 通説の「ハッシュは O(1)」は、この文の後半だけを取り出したもの。 - 衝突は必ず起きる。 バケットより鍵の種類が多いから。規格・javadoc・CPython のコメントはいずれも衝突を前提に書かれている。
- 平均 O(1) は仮定つき。 javadoc は
assuming the hash function disperses the elements properly among the buckets、CPython はthe odds are solidly in our favor。 - 負荷率の上限は処理系ごとに違う(Java 既定 .75 / CPython 3.12 は 2/3 / C++ 規格は構築時 1.0)。0.75 の根拠は
a good tradeoff between time and space costsまでで、最適性の導出は無い。 - 実測: 全衝突なら時間は n にほぼ比例(n=3200 で約1386倍差)。リハッシュ1回は約18535倍だが、起きるのは 0.0085%。「合計で割れば安い」と「1回ごとに安い」は別の主張。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
「辞書を使っているので検索は O(1) です」という説明に対して、最も適切な受け止め方はどれですか。
用語集(3語)
- バケット / 衝突
- バケットはハッシュ値から決まる置き場所の区画。衝突は異なる鍵が同じバケットに入ること。バケット数より鍵の種類が多いので必ず起きる。
- 負荷率 (load factor)
- バケットあたりの要素数の平均。上限を超えるとバケット数を増やして作り直す。上限値は処理系ごとに違い、Java は既定 .75、CPython 3.12 は 2/3、C++ 規格は構築時 1.0(変更可能)。
- 平均 と 最悪
- 平均は入力の分布を仮定したうえでの計算量、最悪は仮定を置かない上限。ハッシュ表の検索は平均 O(1) / 最悪 O(n) で、同じ操作の別々の側面を指す。