從鏈式散列表中有效地選取一個隨機元素？

Question

只是爲了實踐（而不是作爲一個家庭作業），我一直在試圖解決這個問題（CLRS，第3版，運動11.2-6）：

在哈希表假設我們有存儲N個按鍵大小爲m，其中 通過鏈接解決了碰撞，並且我們知道每個鏈的長度，包括最長鏈的長度L.描述從散列表中的密鑰 中隨機一致地選擇一個密鑰並在期望的時間O（L *（1 + m/n））中返回它的過程 。

我到目前爲止認爲每個密鑰返回的概率是1/n。如果我們試圖得到1到n之間的一個隨機值x，並嘗試按照先按桶排序然後沿着桶中的鏈找到第x個鍵，然後用O（m）通過去找到正確的桶通過逐個桶和O（L）時間來獲得鏈中的正確密鑰。

Answer 1

重複返回下列步驟，直到一個元素：

• 隨機選擇一個桶。假設k是存儲桶中的元素數量。
• 從1 ... L統一隨機選擇p。如果p <= k則返回桶中的p th元素。

應該清楚的是，該過程隨機返回一個元素。我們對排列在二維數組中的元素應用拒絕採樣。

每個桶的元素預期數量爲n/m。採樣嘗試成功的概率是(n/m)/L。因此需要查找桶的嘗試次數爲L * m/n。與從桶中檢索元素的O(L)成本一起，預計運行時間爲O(L * (1 + m/n))。