__Hash Table__: Hash table is a method/mechanism of finding a record in a table/list using a key. Suppose we have n record and m key values where m >= n then it for every key if there exist a record n then it a hash table where m is a hash key.

__Hash key__: Hash key is a unique number which can be converted to a record in a record in a hash table.
Here there is a mapping function h(m) which maps each hash key to corresponding records. This function is called hash function.

__Hash function__: Hash function is a mapping function of hash table which takes the key number as input and gives out the index of the record.

n = h(m) (where m >=n)

Here is a very simple hash function like mod. Suppose we have maximum 10 records. Then we can easily map key to index of record n by mod(m). It directly gives us the record number.

n = mod 10 (m)

In a perfect hash table where m >=n there is always record index for a key. When m > n then more than one key may map to a same record. This situation is called hash collision.

__Hash collision__: If more than one hash key can be mapped to a single record in a hash table then it is called has collision.
Example: Say in our example key values ranges from 0 to 9. If we take 10 or more as key then say key m=1 corresponds to record n=1. Now key m=11 also maps to the same record as mod10(11)=1.

There are three popular techniques to avoid collision

- Linear probing,
- Chaining,
- Re-hashing

__Linear probing__

In linear probing records are placed to the next neighborhood of the colliding record.

__Chaining__

Chaining is the technique to remap colliding record to a new linked list chain.

__Re-hashing__

Re-hashing is the second level of hash table with these new colliding records.

**About our authors**: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.