C Program To Create Hash Table using Linear Probing
Learn How To Create Hash Table in C Programming Language. This Program For Hashing in C Language uses Linear Probing Algorithm in Data Structures. Hash Tables are also commonly known as Hash Maps. The functions such as Insertion, Deletion and Searching Records in the Hash Tables are included in the following Hash Table Program.
There are different Searching Algorithms such as Linear Search and Binary Search in which the search time is dependent on the Number of Elements. In Hash Tables, less key comparisons are made which thereby helps to perform search operation in a Constant Time. Therefore, the Search Time is not dependent on the Number of Elements.
Hash Table Concept
The process of converting a key to an Address (Index Position of an Array) is called Hashing or Key To Address transformation done through Hash Functions.
We require a method through which we can convert the key into an integer within a range, and this converted value can be used as index of the array. Instead of taking the key equal to the array index, we can compute the array index from the key.
A Hash Function is used to generate an address from a key or we can say that each key is mapped on a particular index through the hash function. This Hash Function takes key as an Input and returns the Hash value of that key which is used as the address for storing the key in the array. This implementation of Hash Table using Linear Probing method uses Open Addressing method.
C Program For Hash Table in Data Structures using Linear Probing
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 | #include<stdio.h> #include<stdlib.h> #define LIMIT 30 enum record_status {EMPTY, DELETED, OCCUPIED}; struct Employee { int employee_id, employee_age; char employee_name[30]; }; struct Record { struct Employee info; enum record_status status; }; int hash_function(int key) { return (key % LIMIT); } int search_records(int key, struct Record hash_table[]) { int count, temp, position; temp = hash_function(key); position = temp; for(count = 1; count != LIMIT - 1; count++) { if(hash_table[position].status == EMPTY) { return -1; } if(hash_table[position].info.employee_id == key) { return position; } position = (temp + count) % LIMIT; } return -1; } void insert_records(struct Employee emprec, struct Record hash_table[]) { int count, position, temp; int key = emprec.employee_id; temp = hash_function(key); position = temp; for(count = 1; count != LIMIT - 1; count++) { if(hash_table[position].status == EMPTY || hash_table[position].status == DELETED) { hash_table[position].info = emprec; hash_table[position].status = OCCUPIED; printf("\nRecord Inserted into Hash Table\n"); return; } if(hash_table[position].info.employee_id == key) { printf("\nDuplicate Record cannot be Inserted\n"); return; } position = (temp + count) % LIMIT; } printf("\nHash Table Limit Exceeded\n"); } void display_records(struct Record hash_table[]) { int count; printf("\nHash Table\n"); for(count = 0; count < LIMIT; count++) { printf("[%d]:\t", count); if(hash_table[count].status == OCCUPIED) { printf("Occupied - ID: %d Name: %s Age: %d",hash_table[count].info.employee_id, hash_table[count].info.employee_name, hash_table[count].info.employee_age); } else if(hash_table[count].status == DELETED) { printf("\nRecord is Deleted\n"); } else { printf("\nHash Table is Empty\n"); } } } void delete_records(int key, struct Record hash_table[]) { int position = search_records(key, hash_table); if(position == -1) { printf("\nKey Not Found\n"); } else { hash_table[position].status = DELETED; } } int main() { int count, key, option; struct Record hash_table[LIMIT]; struct Employee emprec; for(count = 0; count <= LIMIT - 1; count++) { hash_table[count].status = EMPTY; } while(1) { printf("1. Insert a Record\n"); printf("2. Delete a Record\n"); printf("3. Search a Record\n"); printf("4. Display All Records\n"); printf("5. Exit\n"); printf("Enter Your Option:\t"); scanf("%d", &option); switch(option) { case 1: printf("\nEnter Employee ID:\t"); scanf("%d", &emprec.employee_id); printf("Enter Employee Name:\t"); scanf("%s", emprec.employee_name); printf("Enter Employee Age:\t"); scanf("%d", &emprec.employee_age); insert_records(emprec, hash_table); break; case 2: printf("\nEnter the Key to Delete:\t"); scanf("%d", &key); delete_records(key, hash_table); break; case 3: printf("\nEnter the Key to Search:\t"); scanf("%d", &key); count = search_records(key, hash_table); if(count == -1) { printf("\nRecord Not Found\n"); } else { printf("\nRecord Found at Index Position:\t%d\n", count); } break; case 4: display_records(hash_table); break; case 5: exit(1); } } return 0; } |
Output
In case you get any Compilation Errors in this Hash Tables C Program using Array and Structures or if you have any doubts about it, let us know about it in the Comment Section below.
This is such a simple program for Hashing Implementation. Thanks.
Which other Algorithms are used for Hashing Implementation, especially in C Programming?
1. Division Remainder Method
2. Folding Method
3. Radix Transformation Method
4. Digit Re- arrangement Method
You’rr welcome Rajesh.
Are these Algorithms used in real-world?
I am not sure whether these algorithms are used in realtime! But, there are many advanced algorithms such as these:
1. MD2 (Message Digest Algorithm 2)
2. MD4 (Message Digest Algorithm 4)
3. MD5 (Message Digest Algorithm 5)
4. Secure Hash Algorithm (SHA)
Instead of implementing hash tables using structures, can we implement hash table using Arrays?
I think separate chaining is better than linear probing method for hash table in C programming.
Does linear probing use Open Addressing for Hash Table implementation?
Can we implement hash table using linked list in c programming?
It is one of the simplest hash table implementation in c i have seen. Hash tables using structures are less efficient than the hash tables that use linked lists.
What is the difference between Hash Table using Linear Probing and Separate Chaining methods?
The searching technique that takes O(1) time complexity to find a data or element in an array or a list is Hashing. Therefore, it is really fast.
A hash table in which the hash function is the last few bits of the key and the table refers to buckets is called as Extendible hashing.