· 開発

ハッシュテーブルが O(1) でなくなるとき：衝突、O(n²) の挿入、ハッシュフラッディング

dict や HashMap の O(1) は期待値です。全キーのハッシュ値が同じだと n 個の挿入に少なくとも n(n−1)/2 回の比較が要る理由と、Python のハッシュランダム化と PYTHONHASHSEED、Rust の SipHash、Java の Comparable による対策をまとめました。

開発アルゴリズムデータ構造セキュリティ

ハッシュテーブルの検索と挿入は O(1) だと習います。公式ドキュメントを読むと、この説明には条件が付いています。

Rust 標準ライブラリのコレクションのコスト表は、HashMap の get と remove を O(1)~、insert を O(1)~* と書いています。~ は期待（expected）コスト、* は償却（amortized）コストを表す記号です。ハッシュの確率的な性質のため、可能性は非常に低いものの期待コストよりずっと悪くなることがある、という注記もあります。Java SE 21 の HashMap のドキュメントは、get と put が定数時間だとしたうえで「ハッシュ関数が要素をバケットに適切に分散させると仮定すれば」という条件を付けています。

この仮定が崩れると何が起きるのか、誰かが意図的に崩そうとしたときに言語ランタイムがどう防ぐのかを整理します。基準にしたのは Python 3.15 のドキュメント（2026年10月10日更新）、Rust 1.99.0 のドキュメント、Java SE 21 の API ドキュメントです。

ハッシュ値が同じなら、残る手段は比較だけ

ハッシュテーブルはキーのハッシュ値で格納位置を決めます。ハッシュ値が違う2つのキーは等しくなりえないので、すぐに読み飛ばせます。ハッシュ値が同じなら、ハッシュだけでは区別できないので、キー同士を直接比較するしかありません。Python のデータモデルのドキュメントが求めている性質も一方向だけです。等しいと比較されるオブジェクトはハッシュ値が同じでなければならない、というもので、ハッシュ値が同じなら等しいという保証はありません。

極端な場合を考えます。異なる n 個のキーのハッシュ値がすべて同じだとします。

  • k 番目のキーを入れるとき、テーブルにはすでに k−1 個のキーがあり、どれもハッシュ値が同じです。
  • 新しいキーがすでにあるかどうかを判定するには、その k−1 個と1つずつ比較しなければなりません。比較せずに飛ばしたキーが1つでもあれば、それが新しいキーと等しい可能性を否定できません。
  • したがって n 個すべてを入れるのに必要な比較は、少なくとも 0 + 1 + … + (n−1) = n(n−1)/2 回です。

この下限は n が 1,000 なら 499,500 回、10,000 なら 49,995,000 回です。入力が10倍になると下限は約100倍になる Θ(n²) です。検索も同じで、同じハッシュと等価比較のモデルでは、存在しないキーを探すと少なくとも n 回の等価比較をしてようやく「ない」とわかります。この議論は、キーに対してハッシュと等価比較しか使えないという前提に立っています。後で見る Java のように、キーの大小関係も使えるなら、この議論はそのままでは当てはまりません。

Python では、__hash__ が定数を返すようにするだけでこの状況を作れます。

class Key:
    eq_calls = 0

    def __init__(self, v):
        self.v = v

    def __hash__(self):
        return 42  # すべてのキーのハッシュ値が同じ

    def __eq__(self, other):
        Key.eq_calls += 1
        return isinstance(other, Key) and self.v == other.v

n = 1000
d = {Key(i): i for i in range(n)}
print(Key.eq_calls, n * (n - 1) // 2)

上の議論が与えるのは __eq__ の呼び出し回数の下限です。CPython が正確に何回呼ぶかは dict の実装次第なので、この記事では数値を断定しません。実行して2つの値を比べてみてください。実際のコードでこのような __hash__ を書くと、結果は正しいままでも dict や set がリスト並みに遅くなります。Python のドキュメントは、比較に使う属性をタプルにまとめて hash((self.name, self.nick, self.color)) のようにハッシュすることを勧めています。

入力を選べるのが攻撃者のとき

定数のハッシュは自分で招くミスです。より厄介なのは、ハッシュ関数自体には問題がなく、入力を外部から選べる場合です。キーを決める側が、ハッシュ値が同じ異なるキーを大量に作り出せるなら、サーバーがそれを dict に入れるときに上と同じ状況になります。上のモデルでは、少なくとも n(n−1)/2 回の等価比較が必要です。この攻撃はハッシュフラッディングと呼ばれ、Rust のドキュメントでは HashDoS という名前で出てきます。

Python のドキュメントはハッシュのランダム化を説明する箇所で、その目的を「dict の挿入の最悪性能である O(n²) を突くよう慎重に選んだ入力によるサービス拒否を防ぐため」と書き、2011年の oCERT の勧告（oCERT-2011-003）にリンクしています。

Python：str と bytes のハッシュに秘密の値を混ぜる

Python 3.3 からハッシュのランダム化がデフォルトで有効です。ドキュメントによると、str と bytes の __hash__() の値には予測できないランダムな値が「ソルト」として混ぜられます。1つのプロセスの中では値は変わりませんが、Python を起動し直すと変わります。攻撃者がサーバープロセスの秘密の値を知らなければ、衝突する文字列を前もって計算できない、という考え方です。

この動作は環境変数 PYTHONHASHSEED で変えられます。

  • 設定しないか random にすると、ランダムなシードを使います。
  • 0 から 4294967295 までの10進整数を指定すると、その値を固定シードとして使います。ドキュメントが挙げる用途は、インタープリタ自身のセルフテストのようにハッシュを再現したい場合と、複数の Python プロセスでハッシュ値を共有したい場合です。
  • 0 を指定するとハッシュのランダム化が無効になります。

テスト結果を再現するために入れた PYTHONHASHSEED=0 が本番環境の設定にまで紛れ込むと、この防御がなくなります。固定シードも、その値が知られれば同じことです。

ランダム化には副作用もあります。ハッシュ値が変わると set の反復順序が変わります。Python のドキュメントは、set の順序を保証したことはなく、32ビットと64ビットのビルドの間でもよく違うと書いています。実行のたびに set の表示順が違うのはバグではなく、この機能のためです。使われている文字列ハッシュのアルゴリズム名は sys.hash_info.algorithm で確認できます（3.4 以降）。

整数キーはランダム化の対象外

ドキュメントがソルトの対象として挙げている型は str と bytes です。数値のハッシュは別の規則で決まっています。有理数のハッシュは固定の素数 P による剰余で定義され、CPython は C の long が64ビットの環境で P = 2**61 − 1 を使います（sys.hash_info.modulus）。負の数は符号を付け、結果が −1 なら −2 に置き換えます。

整数は分母が1の有理数なので、この規則をそのまま当てはめると、0 以上の整数 m のハッシュは m mod P になります。すると64ビットの CPython では次が成り立ちます。

import sys

P = sys.hash_info.modulus      # 64ビットの CPython では 2**61 - 1
assert hash(P) == hash(2 * P) == hash(3 * P) == 0
assert hash(-1) == -2

P の倍数はすべてハッシュ値が 0 で、この値は実行のたびに変わったりしません。外部からの入力がそのまま整数の dict キーになるコードは、ハッシュのランダム化では守られないということです。その場合の防御の1つが、後で触れるキー数の制限です。

Rust：デフォルトのハッシャーは HashDoS を想定して選ばれている

Rust 1.99.0 のドキュメントによると、HashMap のデフォルトのハッシュアルゴリズムは HashDoS 攻撃への耐性を考えて選ばれたもので、ランダムなシードを使います。シードはホストが提供する安全な乱数源から作るよう最善を尽くしますが、起動直後のようにシステムのエントロピーが異常に少ないときに作られたシードは品質が低いことがある、とドキュメント自身が警告しています。

現在のアルゴリズムは SipHash 1-3 で、いつでも変わりうると明記されています。整数のような小さなキーや長い文字列のような大きなキーでは他のアルゴリズムのほうが速いものの、そうしたアルゴリズムはたいてい HashDoS を防がない、とも書かれています。速度のためにハッシャーを替える前に、キーが外部からの入力で決まるかどうかを確かめる必要があります。

Java：同点の区別にキーの順序を使える

Java SE 21 の HashMap のドキュメントは、同じ hashCode() を持つキーを多く使うのは、どんなハッシュテーブルでも確実に遅くする方法だと書いています。その影響を和らげるため、キーが Comparable であれば、キー同士の比較順序を同点の区別に役立てることがある（may）と説明しています。

先ほどの n(n−1)/2 という下限は、等価比較しか使えない前提から出たものでした。Java のドキュメントは比較順序を使うことがあると述べるだけで、どう使うかは説明していません。String は Comparable<String> を実装しているので、この扱いの対象になりえます。ドキュメントが「may」と書いている以上、実際に使われる条件やコストの上限は API の約束ではありません。

コードで確認すること

  • 独自の __hash__ では、等価比較に使うフィールドすべてをタプルにまとめてハッシュします。定数や一部のフィールドだけを使うハッシュは衝突を増やします。
  • Python の本番環境で PYTHONHASHSEED=0 や知られた固定値を使いません。set の反復順序に依存するコードも書きません。
  • Python の整数のハッシュはランダム化されません。外部入力が決める整数キーには、リクエストやリソースに見合った制限を設けます。
  • Rust でデフォルトのハッシャーをより速いものに替える前に、キーが信頼できない入力から来ないかを確認します。
  • 1つのリクエストが外部入力から作れるキーの数を制限すると、攻撃者が引き起こせる処理の量も限られます。リクエストやリソースに見合った上限を決めておきます。

ハッシュ関数そのものの性質と暗号学的ハッシュとの違いは「ハッシュ関数とは」で扱いました。平均と最悪が大きく分かれる別の例として「クイックソートが O(n²) になるとき」があり、表の * が表す償却コストは「動的配列と償却計算量」で説明しています。

ブログへ