Algorithm – effectively pick a random element from the linked hash table?

Just for practice (not homework), I have been trying to solve this problem (CLRs, 3rd Edition, exercise 11.2-6):

So far, I think the return probability of each key is 1 / N. if we try to get the random value x between 1 and N, and try to sort by bucket first, and then find the x-th key along the chain in the bucket, then we will find the appropriate bucket by performing o (m), and obtain the correct key in the chain by bucket by bucket and O (L) time

Solution

Repeat the following steps until an element is returned:

>Select a bucket at random Let K be the number of elements in the bucket. > Randomly select P uniform from 1... L If P < = k, the P th element in the bucket is returned It should be clear that the process returns an element randomly and evenly We apply reject sampling to elements arranged in a 2D array

The expected number of barrels is n / m. The probability of successful sampling attempts is (n / M) / L. therefore, the number of attempts required to find a bucket is L * m / N. together with the O (L) cost of retrieving elements from the bucket, the expected running time is O (L * (1 m / N))