# Testbook Test Series: Programming & DS - Hashing

124 views

How to solve such kind of questions ?

Can anybody tell what's is the concept behind this ??

someone provide me link so that I read it and understand the actual  concept

in DS
recategorized
0
5?
0
No bro it's 6
0

Yes its should be 6 i forgot about the last access..

My thought:

In load factor $\frac{n}{m}$ => I have total $'n'$ numbers inserted into a hash table which has $'m'$ slots.

So if we have to declare it as an unsuccessful probe, in the worst case scenario all the $'5'$ elements are one after the other i.e. we have to probe all those $n slots$ first where you will find all are mismatched and in the next attempt you find the blank after seeing this we say that the element is not in the hashtable

So total will be n+1=> worst case for unsuccessful attempts.

1
0
Yes you are right $\frac{1}{1-\alpha}$ where $\alpha$ is load factor.

But the biggest worry for me how to remember these formulae :(

Number of probes in unsuccessful search  = $\displaystyle \frac{1}{1-x}$
where x= load factor of hash table
since, x = $\displaystyle \frac{5}{6 }$

Therefore using above formula , x= $\displaystyle \frac{5}{6 }$ , as no. of probes in unsuccessful  search= 6.

## Related questions

1 vote
1
232 views
The keys 44, 63, 29, 78, 23, 6, 81, 14, 13, 12 and 52 are inserted into an initially empty hash table of length 12 using linear probing with hash function h(k)= k mod 12. What is the probability that the 10th slot will be filled next? i. 11/12 ii. 1 ... slot is left which have a probability of filling as 1 because no matter what index we get for the next insert we are going to fill 10th slot only.