概念・定理図鑑 · 基礎から応用へ

鳩の巣原理:衝突が避けられない条件を数える

対象数と入れ先の数を比較し、ハッシュ衝突や一般化した下限を正確に読み取ります。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 数える対象と入れ先を決める
  2. 余りの種類から重複を示す
  3. 一つの入れ先に何個以上か
  4. ハッシュ値の数と入力の数を比べる
  5. 必要条件を十分条件と取り違えない
  6. 見つけた組を検算する
  7. この記事をロゲイアに質問する理解を確かめる

数える対象と入れ先を決める

鳩の巣原理は、n個の入れ先へn+1個以上の対象を入れると、少なくとも一つの入れ先に二個以上が入るという主張です。対象を鳩、入れ先を巣箱にたとえますが、実際には整数の余り、文字列のハッシュ値、曜日などへ幅広く使えます。最初にどれを対象、どれを入れ先として数えるのかを明示します。対象の区別が曖昧だったり、入れ先が想定より多かったりすると、正しい原理を使っても結論が対象の問題へ当てはまりません。少なくとも一つという存在の主張であり、どの入れ先かを特定する手順をそのまま与えるものではありません。

余りの種類から重複を示す

任意の6個の整数を5で割った余りへ分類するとします。余りの種類は0、1、2、3、4の五つなので、少なくとも二つの整数が同じ余りになります。その二数の差は5で割り切れます。整数の値が大きいか、連続しているかはこの議論に不要です。一方、5個しか選ばなければ、五つの余りが一度ずつ現れる可能性があるため、同じ結論は強制できません。どの一組が該当するかは、実際の値を分類して見つけます。原理は値を計算せずに存在を示し、分類の手順は具体的な組を得る役割を持ちます。

一つの入れ先に何個以上か

m個の対象をn個の入れ先へ割り当てるなら、どこか一つには少なくとも⌈m/n⌉個が入ります。例えば10件を3台のワーカーへすべて割り当てるなら、少なくとも一台は4件以上を持ちます。全台が3件以下なら合計は9件以下になり、10件を置けないためです。これは負荷の件数についての下限であって、処理時間が均等であることや、最も重いワーカーがちょうど4件で済むことまでは保証しません。一件ごとの費用が違う場合、件数の配分と計算時間の配分は異なります。式の結論が何の単位について述べているかを確認します。

ハッシュ値の数と入力の数を比べる

kビットのハッシュ値は最大2のk乗通りです。それより多くの異なる入力を同じ出力空間へ写すなら、必ず衝突する入力が存在します。暗号学的なハッシュ関数も、入力の候補が出力より多ければ衝突の存在そのものを避けられません。安全性で重要なのは、衝突が存在するかだけでなく、攻撃者が現実的な費用で見つけられるかです。さらに、入力を少数しか試していない段階でも衝突は起こり得ます。確率を知りたいなら、値の分布や独立性を置いた別の確率モデルが必要になります。有限個の箱があるという事実だけから、任意の試行回数での衝突確率は計算できません。

必要条件を十分条件と取り違えない

対象数が入れ先数以下だからといって、衝突がないとは限りません。3件を5箱へ入れても、三件すべてを同じ箱へ入れることはできます。原理は一定数を超えたときに衝突を強制するのであって、それ未満での衝突を禁止する規則ではありません。また、同じ箱へ入った対象が、業務上も同じ対象であるとは限りません。ハッシュ表ではハッシュ値が同じでも、元のキーを比較して区別する必要があります。結論を使うときは、存在が分かっただけか、実際の組まで特定したか、その組がアプリのどの条件を満たすかを順に確かめます。

見つけた組を検算する

6個の整数の余りを保存し、すでに見た余りが現れたら、その二数を取り出せます。例えば7と12なら差は5で、確かに5の倍数です。存在の証明と具体的な証人の検算を分けると、剰余演算の扱いや入力の重複を実装で確認しやすくなります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 13

学習コースから次を選ぶ