ハッシュ衝突の期待値

n個の相異なる鍵をm個のバケットへ一様にハッシュすると、負荷率が控えめでさえ、一部の鍵は同じ枠を共有します。直感は占有を過小評価します。誕生日のパラドックスで少なくとも一組が衝突する確率を思い出し、その確率を個数であるかのように扱うのです。このハッシュ衝突の期待値計算機は、別の計画上の問いに答えます。古典的な玉入れモデルを用い、各要素がm個のバケットのうち一つを独立かつ一様に選び、衝突する鍵の期待個数、すなわち自分のバケットで独りではない鍵の数を返します。その主指標に加え、単独の鍵、使用中と空のバケット、最初の入居者を超える溢れ鍵、対ごとの衝突、負荷率n割るmを報告します。演算は対数空間で評価する閉じた恒等式で、完全に決定的であり、モンテカルロ標本も言語モデルも使いません。ハッシュ表の寸法決め、負荷率の調整、32ビットのハッシュ空間とより狭い空間の比較、あるいはメモリを確保する前に教科書の占有主張を確かめる用途にご利用ください。

玉入れモデルで衝突する鍵の期待値が測るもの

n個の玉を独立かつ一様にm個の箱へ投げ入れると、一様ハッシュの標準モデルになります。衝突する鍵とは、少なくとももう一つの玉と同じ箱を共有する玉です。これは少なくとも二つの玉が箱を共有する誕生日のパラドックスの確率とは別の量であり、対ごとの一致数とも違います。

容量計画では普通、個数が欲しくなります。平均して何個の鍵が専用枠を得られないか、他が溢れる一方で何個のバケットが空のままか、最初の入居者の上に何個の余分な鍵が積もるかです。期待値の線形性により、シミュレーションなしできれいな答えが出ます。

任意の一つの鍵を固定してください。残りのn引く一個は、その鍵のバケットを確率いち引くいち割るmで外すので、選んだ鍵が単独である確率は(1 − 1/m)のn引く一乗です。nを掛ければ単独鍵の期待個数です。

nから引けば衝突する鍵の期待個数、すなわちnかけるいち引く(1 − 1/m)のn引く一乗です。同じ占有の議論から、空バケットの期待個数はmかける(1 − 1/m)のn乗となり、したがって使用中バケットも得られます。溢れ鍵は各使用中バケットの最初を超える要素で、n引く使用中に等しいです。

対ごとの衝突はn個から二つを選ぶ数をmで割ったもので、特定の対が同じ場所に落ちる確率がいち割るmだからです。負荷率は単にn割るmです。これらの数値を合わせると、提案した表がバケット不足か、単に忙しいだけか、より大きなmで取り除ける鎖長の税をすでに払っているかが分かります。

入力契約、数式、数値安定性、誤り

必須の整数を二つ送ってください。nは要素数、mはバケット数です。どちらも公開された範囲内の有限整数である必要があります。

nは一から一兆まで、mも一から一兆までで、教室の例、メモリ上の対応表、四十二億九千四百九十六万七千二百九十六枠の完全な32ビットハッシュ空間をカバーします。検証のあと、エンジンはいち引くいち割るmの冪を、指数かけるマイナスいち割るmのlog1pの指数関数として対数空間で評価します。

そのため大きなnとmが、素朴な掛け算の繰り返しのように静かな零へアンダーフローしません。特殊な場合は厳密です。 要素が一つなら決して衝突しません。バケットが一つで要素が二つ以上ならすべての鍵が衝突します。

指数が零のときは一とみなし、(1 − 1/m)の零乗が不定な零の零乗にならないようにします。

容量計画、上限、料金、数値が役立つ場面

表の大きさを選ぶとき、負荷率を比べるとき、負荷率いちでも多くの鍵がバケットを共有する理由をチームに説明するときは、ブラウザの道具をお使いください。衝突する鍵の期待値や溢れ鍵がサービス水準の予算を下回るまでmを上げ、成長のための余裕を残してください。何らかの衝突が存在する確率も必要な場合は、誕生日のパラドックスの確率と対比してください。

その確率は、衝突する鍵の期待個数が大きくなるよりずっと前にいち近くへ飽和するため、二つの道具は別の用件に答えます。結果は完全に決定的です。同じnとmは常に同じ占有ベクトルを返すので、試験や教材に例を固定できます。

言語モデルも外部の統計サービスも乱数性もありません。正確な玉入れの恒等式を、いつまでも落ち着かない近似標本のヒストグラムより好む場合は、ハッシュ表の教程、キャッシュ断片の計画、ブルームに近い占有確認、プログラミング面接の神託へこの端点をつないでください。