Question

Suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly n=1000 character strings and we don’t mind examining an average of 3 elements in an unsuccessful search. If we choose the division method to design the hash function:

1) What is the load factor?

2) What value of 'm' should be picked? (m is the number of slots in the hash table) Explain briefly why you pick this m.

Answer 1

Given a hash table T with m slots that stores n elements, we define the load factor for T as n/m, that is, the average number of elements stored in a chain.

Here we want average length of chain to be 3 so load factor is 3.

B)

N=1000

Load factor =3

N/m=3

M=334

So we 334 slots in our hash table  

THUMBS UP IF YOU ARE SATISFIED WITH ANSWER OTHERWISE REPLY WITH YOUR CONCERN