Consider a hash table with m slots that uses open addressing with linear probing. The table is initially empty. A key k1 is inserted into the table, followed bykey k2, and then key k3. What is the probability that the total number of probes while inserting these keys is at least 4?
1. if 1st 2 keys collide
2. if 1st 2 keys don’t collide ,1st key and 3rd key collide
3. if 1st 2 keys don’t collide , 2nd key and 3rd key collide
Since the insertion of each element requires at least one(Its only one on this term) probe, for there to be 4 probes, there needs to be at least one collision.
If the first two keys collide, we do not even need to know where the third key hashes to – there is already a collision. The probability that the first two keys collide is 1/m.
If the first two keys do not collide, then the third key needs to hash to one of the two slots that the first two keys hash to in order for there to be a collision. The probability of this happening is the product of the probability that the first two keys do not collide and the probability that the third key goes into one of the two slots that the first two keys hash to: (m-1)/m *2/mThe total probability of having at least 4 probes is
1/m + (m-1)/m *2/m
RESOURCE : MIT Handout