CODEWITHSUNDEEP
hashhashtablehash-collision
Core_Dumped
Core_Dumped

Reputation: 4699

Why does increasing size of hashtable decrease the number of collisions?

From what I have read online, there are two ways of decreasing the number of collisions:

  1. Use a better hash function
  2. Increase the size of your hashtable

I can understand the first reason but I cannot seem to get my head around the second.

If lets say I have 5 keys all whose hashes are the same. Lets say we are using chaining for collision resolution. All 5 keys will form a chain starting from the index that equals the hash value. Now, lets say I double the size of the table and rehash all the 5 keys. The 5 keys will still hash to the same index and will still form a change of size 5. How did increasing the size of hash table decrease collisions?

Upvotes: 0

Views: 3135

Answers (2)

Core_Dumped
Core_Dumped

Reputation: 4699

I figured out.

The Hashing has two parts: hash function and compression function. Changing the size of the hash table will change the compression function hence leading to the keys being allotted to different buckets.

Upvotes: 0

Ankit Jain
Ankit Jain

Reputation: 43

This is because while calculating hash it also take the consideration of array size. So while calculating hash if array size is big, it take bigger modulo value.

Eg:
Suppose if array size is 3 and pass values are 2 and 5
then 2%3 and 5%3 take same place i.e. 1.

Now take example of array size 5
then 2%5 and 5%5 take different place i.e. 2 and 0 respectively.

So with the increase in hash table size , number of collision decreases.
Hope this explanation help you.

Upvotes: 1

Related Questions