hashing

Question

What is the average number of probe required when inserting an element with load factor alpha (assume uniform hashing)

a) 1 / 1-alpha

b) 1/1+alpha

c)1/alpha

d)2/2-alpha

Comments

Ans A) rt?

---

yes ....how?

---

@srestha explain how?

---

It can be given as k/k-n where k is the no of slots or buckets and n is the no of entries the one big disadvantage of linear probing is this that no of entries cannot be more than 1 thus avg no of probes for a key k is k/k-n which is first one.

Answer 1

answer a) 

The number of elements in a hash table divided by the number of slots gives load factor denoted by alpha. 

With open addressing the load factor cannot exceed 1. 

So ( 1- alpha)  gives no of free slots. 

avg no of probes = total_#slots/#free_slots

= 1 / (1 - alpha) 

Comments

See here we are considering load factor. Expected no of probes before finding an empty slot increases when load factor increases because the more the hash table will be filled, more the no of times probing has to be done to find an empty slot. Now, we are certain to find an empty slot if hash table has atleast one empty slot. The '1' in 1 upon (1 - loadFactor) means we are certain to find an empty slot if and only if loadfactor $\neq$ 1 (Load_factor = 1 means all the entries in the hash table is filled thus expected no of probes becomes infinity.) and (1 - loadFactor) gives fraction of hash table empty. (In hash table there may be primary clusters but it may not be contiguous. So while linear probing we can find an empty slot in O(1) or O(m) where m = size of hash table. Thus, expected no of probes in case of linear probing actually depends on the fraction of empty slots rather on no. of filled slots)

So, expected no of prones is given by $ \frac{1}{1 - \alpha}\ or\ \frac{m}{m-n}$

---

@tuhin

its almost like we are finding the number of succesfull probes ?

---

(1-alpha) doesn’t give number of free slot. [(1-alpha)*number of slots] gives us number of free slot.

Example : number of keys = 3 and number slots = 5 , so alpha = (3/5) and number of free slot =(1-3/5)*5=2 .   correct me If I’m wrong.

Answer 2

Ans is A
please refer page 15 of this PDF

http://www.mi.fu-berlin.de/wiki/pub/Main/GunnarKlauP1winter0708/discMath_klau_hash_II.pdf

Comments

@rachit

GIven an open address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/ 1−α , assuming simple uniform hashing.

this is taken from your given link

so answer should be A right ?

---

Thanks For sharing

Answer 3

we can also go by this method i got in a stanford's coursera  course

Now given is that a(alpha) is the probability of getting the filled blocks , thus (1-a) is the probability of getting the empty blocks.

now let E(N) be the expectation of the average number of probe required when inserting an element .

Thus E(N) comes out to be 1 + (a*E(N)).

here 1 is added for the operation of going and probing while "a" is multiplied so that when the probe comes out. to be having an element already , it can be done all over again and thus E(N) is multiplied

solving E(N)=1 + (a*E(N))

E(N)=1/(1-a). the required answer.