Let’s implement Hashing & HashTable:

image source your basic

When and why do we need HashTable??

Hash Table data structure is used when we have elements in key-value pairs and we want to search, insert, or delete any pair in average constant time.

However, we should keep in mind that the elements are arranged in any irrelevant order in a hash table.

Key Components Required for Hashing:

1. Hash Function: This function converts a key into integer values which serve as the location(array index)where the key-value pair is stored corresponding to that key. A good hash function is one that is fast to compute and if using that hash function there are fewer chances of a collision.

a)A hash function with integer key :

In this case, the hash function will be: hash(key) = key%tablesize. Try keeping table size as a prime number instead of a multiple of 10, this can result in fewer chances of collision

b)A hash function when the key is a string:

We could have mapped the string to the sum of their ASCII value but anagrams would result in a collision then. A better approach is to treat the char of string having base 27 or 37 or any prime number and apply this function.

hash(string key) = sum for all i from 0 to length of string -1 (string[length-i-1]*27^i]%tablesize

implementation of a hash function for string key

2. Hash Table: It is the data structure where actually those key-value pairs are stored. It is an array where the keys are mapped to array indexes.

3. Collision Handling: Since there is a limited memory so sometimes the hash function generates the same integer value corresponding to different keys i.e. same location to store more than one key-value pair and that is collision we try to minimize this collision.

Separate Channing is a good way to handle collision: Here if more than one key-value pair is mapped to the same index we can maintain a linked list to store then. Then the address of the head of the linked list will be stored in the table. So the table will be storing the elements of type node* then the pointer to the hash table will be of the type node**.

Implementation of a node of linked list for separate Channing:

Implementing node class

Class implementation of hashTable:

Implementation of a hash table

Inserting a key-value pair in a hash table:

It follows these steps:

1. Just find the index corresponding to the key with the help of hash function
2. Create a new node passing the key-value pair to it
3. Make that node point to the index of the table which is mapped
4. Store the address of the head of the linked list corresponding to that index in that cell.

Inserting key-value pair in the hash table

Printing the elements of a hash table:

Printing elements of a hash table

The output of the above code

Search elements in a hash table:

In order to decrease collision, we can even implement rehashing i.e. as soon as the ratio of current size to a fixed size of table crosses a particular limit. Then a new table of double size is created and all the elements are shifted from the old table to the new table. This concept is known as rehashing.

End of the article.

Thank you.

Hope it would help..

Happy Coding :)