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!
Posts
No comments:
Post a Comment