Algorithms For Dummies

Avoiding collisions

A problem occurs when two data entries have the same hash value. If you simply 

write  the  value  into  the  hash  table,  the  second  entry  will  overwrite  the  first, 

resulting in a loss of data. Collisions, the use of the same hash value by two values, 

require you to have some sort of strategy in mind for handling them. Of course, 

the best strategy is to avoid the collision in the first place.

One  of  the  methods  for  avoiding  collisions  is  to  ensure  that  you  have  a  large 

enough hash table. Keeping the load factor low is your first line of defense against 

having to become creative in the use of your hash table. However, even with a 

large table, you can’t always avoid collisions. Sometimes the potential dataset is 

so large, but the used dataset is so small, that avoiding the problem becomes 

impossible. For example, if you have a school with 400 children and rely on their 

social security number for identification, collisions are inevitable because no one 

is going to create a hash table with a billion entries for that many children. The 

waste of memory would be enormous. Consequently, a hash function may have to 

use more than just a simple modulus output to create the hash value. Here are 

some techniques you can use to avoid collisions: