Hashing With Chaining

This method maintains a chain of elements that have the same hash address. We can take the hash table as an array of pointers. The size of the hash table can be the number of records. Here each pointer will point to one linked list and the elements which have the same hash address will be maintained in the linked list. We can maintain the linked list in sorted order and each element of the linked list will contain the whole record with a key.

• For inserting one element, first, we have to get the hash value through the hash function which will map in the hash table, then that element will be inserted in the linked list which is shown in the following Figure as an example.

• Searching for a key is also the same, first, we will get the hash key value in a hash table through the hash function, then we will search for the element in the corresponding linked list.
• Deletion of a key contains the first search operation then the same as the delete operation in the linked list.

The main advantage of this hashing is saving memory space and perfect collision resolution. Here hash table contains only pointers that point to the linked list, containing records. So there is no wastage of memory space because of an empty hash table and the hash table size can be taken as a number of records. Hash table space is also minimized because records are stored in the linked list. The elements which have the same hash address will be in the same linked list. So we should use a good hash function that distributes elements on different hash addresses. Basically linked lists will be small, so searching will be fast.

The main disadvantage is also a waste of memory space. In cases where records are very small or contain only a key then the link part for every element in the linked list and pointer space in the hash table will be a waste of memory space.

Source code

#include <stdio.h> #include <stdlib.h> #define MAX 11 struct Record { int data; struct Record *link; }; void insert(struct Record *hash_table[],int); int search_element(int key, struct Record *hash_table[]); void remove_record(int key, struct Record *hash_table[]); void show(struct Record *hash_table[]); int hash_function(int key); int main() { struct Record *hash_table[MAX]; int count, key, option,value; for(count = 0; count <= MAX - 1; count++) { hash_table[count] = NULL; } while(1) { printf("1. Insert a Record in Hash Table\n"); printf("2. Search for a Record\n"); printf("3. Delete a Record\n"); printf("4. Show Hash Table\n"); printf("5. Quit\n"); printf("Enter your option\n"); scanf("%d",&option); switch(option) { case 1: printf("\nEnter the number:"); scanf("%d", &value); insert(hash_table,value); break; case 2: printf("Enter the element to search:\t"); scanf("%d", &key); count = search_element(key, hash_table); if(count == -1) { printf("Element Not Found\n"); } else { printf("Element Found in Chain:\t%d\n", count); } break; case 3: printf("Enter the element to delete:\t"); scanf("%d", &key); remove_record(key, hash_table); break; case 4: show(hash_table); break; case 5: return 0; } } return 0; } void insert(struct Record *hash_table[],int value) { int key, h; struct Record *temp; key = value; if(search_element(key, hash_table) != -1) { printf("Duplicate Key\n"); return; } h = hash_function(key); temp = malloc(sizeof(struct Record)); temp->data = value; temp->link = hash_table[h]; hash_table[h] = temp; } void show(struct Record *hash_table[]) { int count; struct Record *ptr; for(count = 0; count < MAX; count++) { printf("\n[%3d]", count); if(hash_table[count] != NULL) { ptr = hash_table[count]; while(ptr != NULL) { printf("%d-->", ptr->data); ptr=ptr->link; } } } printf("\n"); } int search_element(int key, struct Record *hash_table[]) { int h; struct Record *ptr; h = hash_function(key); ptr = hash_table[h]; while(ptr != NULL) { if(ptr->data == key) { return h; } ptr = ptr->link; } return -1; } void remove_record(int key, struct Record *hash_table[]) { int h; struct Record *temp, *ptr; h = hash_function(key); if(hash_table[h]==NULL) { printf("Key %d Not Found\n", key); return; } if(hash_table[h]->data == key) { temp = hash_table[h]; hash_table[h] = hash_table[h]->link; free(temp); return; } ptr = hash_table[h]; while(ptr->link != NULL) { if(ptr->link->data == key) { temp = ptr->link; ptr->link = temp->link; free(temp); return; } ptr = ptr->link; } printf("Key %d Not Found\n", key); } int hash_function(int key) { return (key % MAX); }

Happy Exploring!