0

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?

Core_Dumped
  • 4,577
  • 11
  • 47
  • 71
  • 1
    see this: https://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions [source: http://javarevisited.blogspot.co.il/2011/02/how-hashmap-works-in-java.html] – AsfK Oct 26 '17 at 06:18

2 Answers2

1

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.

Ankit Jain
  • 43
  • 5
0

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.

Core_Dumped
  • 4,577
  • 11
  • 47
  • 71