title: Efficiently picking a random element from a chained hash table?
body: <p>Just for practice (and not as a homework assignment) I have been trying to solve this problem (CLRS, 3rd edition, exercise 11.2-6):</p>
  
  <blockquote>
    <p>Suppose we have stored n keys in a hash table of size m, with
    collisions resolved by chaining, and that we know the length of each
    chain, including the length L of the longest chain. Describe a
    procedure that selects a key uniformly at random from among the keys
    in the hash table and returns it in expected time O(L * (1 + m/n)).</p>
  </blockquote>
  
  <p>What I thought so far is that the probability of each key being returned is 1/n. If we try to get a random value x between 1 to n, and try to find the xth key in sequence first sorted by bucket then along the chain in the bucket, then it will take O(m) to find the right bucket by going through buckets one by one and O(L) time to get the right key in chain.</p>