將n個項插入到大小爲m的哈希表中時，假設每個項目的目標是獨立均勻隨機的，那麼不發生碰撞的概率是多少？哈希表中的碰撞概率
我的工作迄今： 我們有n項和M的位置。 每個項目有1/m的機會在任何特定的位置。 有nC2種可能的項目對。 沒有碰撞的概率是對於每個位置，每一對物品都不散列到該位置的概率。
對於任何給定的位置，對於任何給定的對，兩個項不散列到該位置的概率是（m-1）/ m。 （（m-1）/ m）^（nC2）。對於任何給定的位置，上述對於所有對的概率爲（（m-1）/ m）^（nC2）。
然後，對於每個位置這種可能性是 [（（m-1）/ m）^（nC2）] ^（m）。
你在這個推理中犯了一些錯誤。主要的一點是，你假設一對不散列在一起的概率是獨立的，所以你可以把它們相乘。你沒有證明是這種情況，事實上情況並非如此。考慮三個元素a，b和c。如果你知道a和b都不與c碰撞，那麼它們被限制在m-1個位置，而不是最初的m個位置，而且如果你忽略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中會更好！）您可以選擇這三個等效表達式中的哪一個最適合您的目的。
當然，還有其他方法可以提供這些表達式。最後一個可以被認爲是沒有碰撞的概率將1個項目放置在m個時隙中放置第二個項目的條件概率放置在沒有先前碰撞時間的情況下給定第三個項目的條件概率。
這些表達式相當容易測試。只要選擇特定的m和n的小值，從那些m中生成n個項目的所有可能選擇，並找出沒有碰撞的經驗概率。這應該與上面的公式一致。我將把編程語言和編碼的選擇留給你。畢竟，這是一個編程站點。我只是在Python中做了這個，對n和m有多種選擇，並且它可以解決。