Hashing

Binary search, Linear search and all other searches key are totally dependent on the number of elements and so many keys comparison are involved.
Now, our need is to search the element in constant time and less key comparison should be involved.
Hashing is a technique where we can store the record or get the record in constant time.

For storing record.  One time process

  •  Key
  •  Generate array index
  •  Store the record on that address

For retrieve the record. Many time process

  • Key
  • Generator index
  • Get the record from that array index
The generation of Array index (hash address) uses hash function, which convert it into array index, the array supports hashing for storing and searching records.
If each key is mapped on a unique hash table address then this situation is called Ideal Situation but maybe possibiliy that our hash function is generating same hash table address for difficult different key, this situation called Collision.
So we have to do 2 important things :
  1. Using a good Hash Function (Hash Technique) which ensure minimum collision.
  2. Resolve the collision.

Choosing a Hash Function

Hash Function which generate the hash address in hash table with the help of key it work like mapping interface between key and hash table.
We have 2 criteria for choosing a good Hash Function.
  • It should be easy to compute and it should generate unique address or it should generate addresses with minimum collision.
  • There are some techniques for choosing a Hash Function. Suppose table size is hundred we will take that to rightmost, leftmost digit for getting hash table.
  1.  Truncation method
  2.  Mid square method
  3.  Holding method
  4.  Modular method
hashing in data structure
Hashing in Data Structure