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)

hash key, hash function, record index

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.

hash collision

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 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.

 Vote 0

Similar topics related to this section

heap, Complexity, Linear Search, Binary Search, Hash Table, Sorting, Bubble Sort, Selection Sort,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan