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
In linear probing records are placed to the next neighborhood of the colliding record.
Chaining is the technique to remap colliding record to a new linked list chain.
Re-hashing is the second level of hash table with these new colliding records.
You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.