各項目の宛先が独立して一様にランダムであると仮定して、n個の項目をサイズmのハッシュテーブルに挿入するとき、衝突が発生しない確率はどれくらいですか？ハッシュテーブルにおける衝突の確率
私がこれまでに取り組んで： は、我々は、n項目とm個の位置を有します。 各アイテムは1/mの確率で特定の場所にいる可能性があります。 nC2可能なアイテムのペアがあります。 衝突が発生しない確率は、すべての場所について、すべての項目のペアがその場所にハッシュしない確率です。
任意の与えられたペアについて、2つのアイテムがその位置にハッシュしない確率は（m-1）/ mです。
次に、任意の所与の場所について、ALL対について上記が成立する確率は、（（m-1）/ m）^（nC2）である。
そして、これがすべての場所に当てはまる確率は、 [（（m-1）/ m）^（nC2）] ^（m）です。
あなたはその推論でいくつかの間違いを犯しました。主なものは、一緒にハッシングしないペアの確率が独立していると仮定しているため、それらを掛け合わせることができます。あなたはそれが事実であることを示しておらず、実際にはそうではありません。 3つの要素a、b、cを考えてみましょう。 aとbの両方がcと衝突していないことがわかっている場合、最初のm個の場所ではなくm-1個の場所に限定され、cを無視した場合よりも互いに衝突する可能性が高くなります。
あなたの希望する確率を見つけるための簡単な方法です。衝突を無視した総可能性を見ると、n個のアイテムのそれぞれにはm個の場所があります。それらのプレースメントは独立しているので、私たちが考慮に入れると、合計可能性はm^n（またはPythonではm ** n）です。
衝突がないことがわかっている場合、これらのn個のアイテムは、m個の場所から置き換えずに選択する方法です。したがって、私たちが考慮に入れると、mPnの可能性が生じます。これは、m個の選択肢からn個の項目を置換せずに、順序（順列）で選択する方法です。したがって、あなたの希望する確率は、
mPn/m^n =（m！）/（mn）！* m^n）= m/m *（m-1）/ m *（m-2）/m * ... *（m-n + 1）/ m
最後の式にはn個の要素があります。 （これはMathJaxのほうがはるかに優れています！）3つの同等の式のうち、どれがあなたの目的に最も適しているかを選択できます。
もちろん、これらの表現には他の方法もあります。その最後のものは、衝突のない確率として与えられ、前の衝突時間が与えられていない第2のアイテムを置くという条件付き確率と、前の衝突時間が与えられていない第3のアイテムを置く条件付き確率とをmスロットに入れる。
これらの式はかなり簡単にテストできます。特定の小さな値のmとnを選択し、それらの中からn個のアイテムの可能なすべての選択肢を生成し、衝突のない経験的確率を見つけます。これは上記の数式と一致するはずです。私はあなたにプログラミング言語とコーディングの選択を任せます。結局のところ、これはプログラミングサイトです。私はちょうどこれをPythonで行いました。nとmの複数の選択肢について、それはうまくいきました。