有關散列表的預期值

我正在處理數據結構教科書中的一個問題，而且我陷入了困境。我有一個16,000個插槽的散列表。它處理＃個城市，並且n = 15937個城市。我試圖弄清楚預計的老虎機數量是多少，只有一個城市，然後兩個城市是一樣的。我知道如何找到每個插槽的預期數量和預期的空插槽數量，但不知道這對我是否有用。每個插槽有插入項目的機會相等。任何人都知道我可以從哪裏開始？有關散列表的預期值

謝謝！

來源

2013-11-21 pfinferno

下手說5個插槽和4個城市，然後看看你推斷16000

關係的第一個城市可以被認爲是在第一個插槽

第二個城市有X％是在第二....

編輯第一槽和X％ - 另一種方式來看待那是什麼都是可能的安排，你看

A1B1C1D1 is all for cities (A,B,C,D) are in bucket 1 
A1B1C1D2 is ABC in bucket 1 and D is in bucket 2 
A1B1C1D3 is ABC in bucket 1 and D is in bucket 3 
A1B1C1D4 is ABC in bucket 1 and D is in bucket 4 
A1B1C1D5 is ABC in bucket 1 and D is in bucket 5 
A1B1C2D1 is ABD in bucket 1 C in bucket 2 
.....

什麼百分比做

希望有幫助

來源

2013-11-21 04:43:17

那麼每個城市有20％的機會在每個插槽的權利？第一個城市進入第一個位置。第二城市每個城市有1/5的機會參加？ – pfinferno

等待，預期的槽位數只有一個城市是（1/16000）* 15937？ – pfinferno

@pfinferno - 這個想法是吹掉整棵樹 - 你可以推導出一個桶中所有4個城市的機會公式，3個城市桶和2個城市桶的數量公式想法是手動解決一個小的數據集，然後工作 –

有關散列表的預期值

回答

相關問題