Learn how to create Hash Table using Separate Chaining in C Programming Language. The separate chaining hash table implementation makes use of Linked List in C Programming. There are different hashing algorithms such as Bucket Hashing, Linear Probing, Separate Chaining, etc.
Hash tables offers finding the element in less key comparisons, making the search operation to execute in a Constant Time. Therefore, the search time for the element is independent of the number of records.
Separate Chaining Concept
In separate chaining implementation of hash tables, linked lists are used for elements that have the same hash address. The hash tables in this scenario does not include the actual keys and records. It contains only an array of pointers where pointer points to a linked list.
All the elements having the same hash address will be stored in a separate linked list and the starting address of that particular linked list will be stored in the index of the hash table. In the chaining method, the comparisons are done only with the keys that have the same hash values.
The disadvantage of Separate Chaining is that it needs an extra space for storing pointers which is dependent on the table size and the records.
C Program For Hash Table using Separate Chaining and Linked List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | #include <stdio.h> #include<stdlib.h> #define MAX 20 struct Employee { int employee_id; char employee_name[45]; int employee_age; }; struct Record { struct Employee data; struct Record *link; }; void insert(struct Employee employee_record, struct Record *hash_table[]); 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]; struct Employee employee_record; int count, key, option; 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("Enter the Employee Details\n"); printf("Employee ID:\t"); scanf("%d", &employee_record.employee_id); printf("Employee Name:\t"); scanf("%s", employee_record.employee_name); printf("Employee Age:\t"); scanf("%d", &employee_record.employee_age); insert(employee_record, hash_table); 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: exit(1); } } return 0; } void insert(struct Employee employee_record, struct Record *hash_table[]) { int key, h; struct Record *temp; key = employee_record.employee_id; if(search_element(key, hash_table) != -1) { printf("Duplicate Key\n"); return; } h = hash_function(key); temp = malloc(sizeof(struct Record)); temp->data = employee_record; 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 %s %d\t", ptr->data.employee_id, ptr->data.employee_name, ptr->data.employee_age); 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.employee_id == 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.employee_id == 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.employee_id == 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); } |
Output
If you have any compilation errors or doubts about C Program For Separate Chaining Hash Table, let us know about it in the comment section below.
This separate chaining algorithm for creating hash table uses Singly Linked List. Can we implement it using Doubly or Circular Linked Lists too?
I was desperately searching how to implement hash table using linked list. Did not get much good answers. Thanks a lot codingalpha.
It is really a simple separate chaining hashing algorithm in c programming. Thanks.
Thanks for the explanation. The Separate Chaining Hash Program in C Language is too simple to understand.