Collision

A collision occurs when the hash function used to index a hash table indices the element of an array to an already pre-existing value. For example, if the has function were a mod function by a value, you would run into collisions eventually.

Example

If our hash function were defined by the following:

int hash(int value){
	return value % 4;
}

This hash would return 1 for a value of 1 or 5 for example. Therefore, the following:

	hash_table ht;
	ht.insert(1);
	ht.insert(2);
	ht.insert(5);

Would cause a collision at the third insert statement. Collisions are a natural and necessary part of hash tables, and they are dealt with varying methods.

Regardless of method, it’s still better to avoid collisions when possible.