在發生碰撞之前，您可以將多少名學生放入哈希表中？

我的教授給我們這個幻燈片，而說明哈希碰撞概率：當我擡起頭具有的「生日悖論」生日相同的兩個人的概率在發生碰撞之前，您可以將多少名學生放入哈希表中？

，我就Wikipedia and other sources的概率發現在n = 10時應該是11.7。實際上，我用他的公式計算出來的每個價值都不同於教授的幻燈片。

所以我的問題是：當他問「在發生碰撞之前我們可以向我們的桌子散列多少學生」，這與計算任何兩名學生有相同生日的概率有什麼不同？

如果是這樣，是否有一個公式呢？

還是他的幻燈片是錯的？

來源

2016-06-13 xChaos

當有疑問時，讓我們來檢查計算！

假設所有結果具有相同的可能性並且彼此獨立，那麼您的導師給出的公式確實是正確的。下面是打印值碰撞的少數學生人數一點點的C程序：

#include <stdio.h> 

const int kNumBuckets = 365; 
const int kMaxNumber = 50; 

int main() { 
    double probability = 1.0; 
    for (int i = 1; i <= kMaxNumber; i++) { 
    probability *= (double)(kNumBuckets - i + 1)/kNumBuckets; 

    if (i % 10 == 0) { 
     printf("Collision probability with %2d students: %g\n", i, 1.0 - probability); 
    } 
    } 
    return 0; 
}

這裏的輸出：

Collision probability with 10 students: 0.116948 
Collision probability with 20 students: 0.411438 
Collision probability with 30 students: 0.706316 
Collision probability with 40 students: 0.891232 
Collision probability with 50 students: 0.970374

這些數字不與你的教授同意，但他們同意維基百科。我會假設這只是你教授材料中的一個錯誤。聯繫他們並要求澄清可能並不會帶來什麼壞處，因爲這可能只是一個誠實的錯誤。

來源

2016-06-13 20:02:31 templatetypedef

那麼問題就會問「在碰撞發生之前，您可以輸入多少個**」。那麼你是說，這與「N個學生有相同生日的概率是多少？」的問題是一樣的。 – xChaos

我評估了你的教授給出的表達。你的好眼光：我沒有得到你發佈的價值。我看到的那些更接近生日問題結果。你是一個思考的好學生，不接受你所說的一切。

/** 
* Implement the expression in the question to check. 
* User: mduffy 
* Date: 6/14/2016 
* Time: 8:03 AM 
* @link http://stackoverflow.com/questions/37798077/how-many-students-can-you-put-into-a-hash-table-before-a-collision-occurs 
*/ 
public class CollisionProbability { 

    public static void main(String[] args) { 
     int m = (args.length > 0) ? Integer.parseInt(args[0]) : 365; 
     int nMin = 10; 
     int nMax = (args.length > 1) ? Integer.parseInt(args[1]) : 100; 
     int dn = (args.length > 2) ? Integer.parseInt(args[2]) : 10; 
     for (int n = nMin; n < nMax; n += dn) { 
      System.out.println(String.format("m=%d n=%d p(collide)=%f", m, n, p(m, n))); 
     } 
    } 

    public static double p(int m, int n) { 
     double p = 1.0; 
     for (int i = 1; i < n; ++i) { 
      p *= (double)(m-i)/m; 
     } 
     return 1.0-p; 
    } 
}

來源

2016-06-14 12:18:16 duffymo

迅速回答不無事生非：

所以我的問題是：當他問：「我們有多少學生可以散列到我們的餐桌碰撞發生前，」是，從計算的不同任何2名學生有相同生日的概率？

不，它沒有什麼不同。 1..365年的日子與擁有365個散列桶的日子完全相同，並且可接受的散列函數包含完全隨機的值（這也是錯誤的，假設在生日問題中）。

如果是這樣，有沒有一個公式呢？

當然，維基百科有它https://en.wikipedia.org/wiki/Birthday_problem。

來源

2016-06-14 13:35:58 AnoE

我認爲你的教授已經完成了M = 181或182的計算，即半年。用這些數值運行計算給出

181, 10, 0.22359889333483407 
181, 20, 0.6636461635832673 
181, 30, 0.9215808021897809 
181, 40, 0.9905555232124136 
182, 10, 0.2224990010873642 
182, 20, 0.6615484583220019 
182, 30, 0.9204086626783813 
182, 40, 0.9902893472869162

來源

2016-06-15 06:01:54

在發生碰撞之前，您可以將多少名學生放入哈希表中？

回答

相關問題