期望散列時的空槽數量

Question

我有n個鍵和一個大小爲n的散列表。

我想弄清楚空插槽的預期數量。

我知道統一的哈希假設表明每個密鑰都可能進入任何時隙。

到目前爲止，我已經提出了n個密鑰，每個密鑰都有n個時隙的相等概率，所以n^2種可能的組合。

我不確定從哪裏去，在正確的方向任何點將不勝感激！ 謝謝。

Answer 1

首先，可能的組合數不n^2但n^n由於每個n鍵具有n可能性在時隙中降落。

接着，由於所有的槽是對稱的，預期數空槽E = n * P的，其中P是每個單時隙結束空的概率。這是由於linearity of expectation即使在隨機值依賴時也是如此。

現在請注意，單個密鑰未出現在此插槽中的概率爲Q爲Q = (n - 1)/n。

由於有n密鑰，所以沒有密鑰在固定槽中着陸的概率P是Q^n。總結一下，我們有E = n * ((n - 1)/n)^n。 (n - 1/n)^n的限制是1/e（see here），因此空槽的預期數目是n/e。