CLRS 11.2-6

Question

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)).

Answer 1

Actually your expected time O(L*(1+$\frac{m}{n}$) )

where (1+$\frac{m}{n}$) always give more than 1 ===>O(L)

you have m slots and n keys ===> use m%n as hashing algorithm

where collision occurs add as a node in linked list

 

while retriving, O(1) you can go that slot, but there you have chain of values(Linked List)

you need to search in Linked List which size is L in worst case ===>O(L)