Hashtable and collision resolution methods

Hashing is basically a data searching method implemented using a data structure called hash table or hash map. A hash table includes a set of keys and values. If the key is given(for example an employee name in an employee database) one can easily find out the records associated with the key. In the hash table the keys are mapped to the location of values(data to be searched) or records using a hash function. That is the key is converted into memory address by passing it through a particular function called hash function. the records are stored in those locations indicated by memory addresses. later when a lookup or search is required, the given key is again passed through the hash function to obtain the location of records where it was previously stored. This eliminates the need for searching the entire records to choose the right one.

Collision :
A state of collision occurs when the hash function maps two different keys to same location. Thus the corresponding records can not be stored in the same location. The methods used to solve the problem of collision is called collision resolution. The two most popular method of resolving collision are,

1. Separate chaining
2. Open addressing

In open addressing new positions are computed using a probe sequence once the collision occurs and the next record is stored in that position accordingly. A link list is used to resolve collision in the second method called chaining.