Hash Table with Linear Probing

Question:

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/m

The total probability of having at least 4 probes is
1/m + (m-1)/m *2/m

RESOURCE : MIT Handout

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s