Hash Table Introduction

Hash Table is a data structure which organizes the data using hash functions in order to support quick insertion and search.


We have two different types of hash tables :

1. HashSet

2. HashMap

-> HashSet is one of the implementation of Set Data Structure with no repeated values.

-> HashMap is one of the implementation of Map Data Structure to store (Key , Value ) pairs.

By using proper hash function the hash table can achieve wonderful performance in both insertion and search.


Principle Behind the Hash Table :

Hash Table is a data structure which supports quick insertion and search using hash functions.

The Key idea of the hash function is to map keys to buckets .

1. When we insert a new key the hash function will decide which bucket the key should be assigned and the key will be inserted into the corresponding bucket.

2. When we want to search for a key , the hash table  will use the same hash function to find the corresponding bucket and search only in the specified bucket.



For Example consider Y = X % 5 is our hash function .


Consider the elements ->  3 . 5 . 6  7  10


All the elements will go through the hash function and will get mapped to the corresponding buckets.

Insertion :

So . 3 will be assigned to bucket with index 3.

       5 . will be assigned to bucket with index 0.

      6   will be assigned to bucket with index 1.
   
      7 will be assigned to bucket with index 2.
 
     10 will be assigned to bucket with index 0.

Search:

We parse the elements through the same hash function and search in the specified bucket.

 If we want to search 23 we will search in bucket 3 as 23%5 is 3.

If we want to search 34 we will search in bucket 4 as 34%5 is 4.