What is Hash Table? Where it is used? Explain Hash Table with C source code.

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.

‹ # ›