Selezionando in modo efficiente un elemento casuale da una tabella hash concatenata?

Question

solo per la pratica (e non come un compito a casa) ho cercato di risolvere questo problema (CLRS, 3a edizione, esercizio 11,2-6):

chiavi Supponiamo di avere immagazzinati n in una tabella hash di dimensione m, con le collisioni risolte dal concatenamento e che conosciamo la lunghezza di ciascuna catena , inclusa la lunghezza L della catena più lunga. Descrivere una procedura che seleziona una chiave uniformemente a caso tra i tasti nella tabella hash e la restituisce nel tempo previsto O (L * (1 + m/n)).

Quello che ho pensato finora è che la probabilità che ogni tasto venga restituito è 1/n. Se proviamo a ottenere un valore casuale x compreso tra 1 e n, e proviamo a trovare la chiave xth in sequenza prima ordinata per bucket e poi lungo la catena nel bucket, allora O (m) richiederà il bucket giusto andando attraverso i bucket uno per uno e O (L) tempo per ottenere la chiave giusta in catena.

Answer 1

Ripetere le seguenti operazioni fino a un elemento viene restituito:

• selezionare casualmente un secchio. Lascia che sia k il numero di elementi nel bucket.
• Selezionare p in modo uniforme a caso da 1 ... L. Se p <= k restituisce quindi l'elemento p nel bucket.

Dovrebbe essere chiaro che la procedura restituisce un elemento in modo uniforme a caso. Stiamo applicando il campionamento del rifiuto agli elementi posizionati in un array 2D.

Il numero previsto di elementi per bucket è n/m. La probabilità che il tentativo di campionamento abbia esito positivo è (n/m)/L. Il numero atteso di tentativi necessari per trovare un bucket è quindi L * m/n. Insieme al costo di recupero dell'elemento dal bucket, O(L), il tempo di esecuzione previsto è O(L * (1 + m/n)).