C Program to Implement Hash Tables with Linear Probing

This is a C Program to Implement Hash Tables with Linear Probing.

Problem Description

A hash table is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots. Due to collision of keys while inserting elements into the hash table, idea of Linear Probing is used to probe the through the subsequent elements (looping back) of array starting from hash code value (index of the key) where key collision occurs.

Problem Solution

1. Create an array of structure (i.e a hash table).
2. Take a key and a value to be stored in hash table as input.
3. Corresponding to the key, an index will be generated i.e every key is stored in a particular array index.
4. Using the generated index, access the data located in that array index.
5. In case of absence of data, create one and insert the data item (key and value) into it and increment the size of hash table.
6. In case the data exists, probe through the subsequent elements (looping back if necessary) for free space to insert new data item.
Note: This probing will continue until we reach the same element again (from where we began probing)
7. To display all the elements of hash table, element at each index is accessed (via for loop).
8. To remove a key from hash table, we will first calculate its index and delete it if key matches, else probe through elements until we find key or an empty space where not a single data has been entered (means data does not exist in the hash table).
9. Exit

Program/Source Code

Here is the source code of the C Program to implement a Hash Table with Linear Probing. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. /* to store a data (consisting of key and value) in hash table array */
  5. struct item 
  6. {
  7.     int key;
  8.     int value;
  9. };
  10.  
  11. /* each hash table item has a flag (status) and data (consisting of key and value) */
  12. struct hashtable_item 
  13. {
  14.  
  15.     int flag;
  16.     /*
  17.      * flag = 0 : data does not exist
  18.      * flag = 1 : data exists
  19.      * flag = 2 : data existed at least once
  20.     */
  21.  
  22.     struct item *data;
  23.  
  24. };
  25.  
  26. struct hashtable_item *array;
  27. int size = 0;
  28. int max = 10;
  29.  
  30. /* initializing hash table array */
  31. void init_array()
  32. {
  33.     int i;
  34.     for (i = 0; i < max; i++) 
  35.     {
  36. 	array[i].flag = 0;
  37. 	array[i].data = NULL;
  38.     }
  39. }
  40.  
  41. /* to every key, it will generate a corresponding index */
  42. int hashcode(int key)
  43. {
  44.     return (key % max);
  45. }
  46.  
  47. /* to insert an element in the hash table */
  48. void insert(int key, int value)
  49. {
  50.     int index = hashcode(key);
  51.     int i = index;
  52.  
  53.     /* creating new item to insert in the hash table array */
  54.     struct item *new_item = (struct item*) malloc(sizeof(struct item));
  55.     new_item->key = key;
  56.     new_item->value = value;
  57.  
  58.     /* probing through the array until we reach an empty space */
  59.     while (array[i].flag == 1) 
  60.     {
  61.  
  62. 	if (array[i].data->key == key) 
  63.         {
  64.  
  65. 		/* case where already existing key matches the given key */
  66. 		printf("\n Key already exists, hence updating its value \n");
  67. 		array[i].data->value = value;
  68. 		return;
  69.  
  70. 	}
  71.  
  72. 	i = (i + 1) % max;
  73. 	if (i == index) 
  74.         {
  75. 		printf("\n Hash table is full, cannot insert any more item \n");
  76. 		return;
  77. 	}
  78.  
  79.     }
  80.  
  81.     array[i].flag = 1;
  82.     array[i].data = new_item;
  83.     size++;
  84.     printf("\n Key (%d) has been inserted \n", key);
  85.  
  86. } 
  87.  
  88.  
  89. /* to remove an element from the hash table */
  90. void remove_element(int key)
  91. {
  92.     int index = hashcode(key);
  93.     int  i = index;
  94.  
  95.     /* probing through array until we reach an empty space where not even once an element had been present */
  96.     while (array[i].flag != 0) 
  97.     {
  98.  
  99. 	if (array[i].flag == 1  &&  array[i].data->key == key ) 
  100.         {
  101.  
  102. 		// case when data key matches the given key
  103. 		array[i].flag =  2;
  104. 		array[i].data = NULL;
  105. 		size--;
  106. 		printf("\n Key (%d) has been removed \n", key);
  107. 		return;
  108.  
  109. 	}
  110. 	i = (i + 1) % max;
  111. 	if (i == index)
  112.         {
  113. 		break;
  114. 	}
  115.  
  116.     }
  117.  
  118.     printf("\n This key does not exist \n");
  119.  
  120. }
  121.  
  122. /* to display all the elements of hash table */
  123. void display()
  124. {
  125.     int i;
  126.     for (i = 0; i < max; i++)
  127.     {
  128. 	struct item *current = (struct item*) array[i].data;
  129.  
  130. 	if (current == NULL) 
  131.         {
  132. 	    printf("\n Array[%d] has no elements \n", i);
  133. 	}
  134. 	else
  135.         {
  136. 	    printf("\n Array[%d] has elements -: \n  %d (key) and %d(value) ", i, current->key, current->value);
  137. 	}
  138.     }
  139.  
  140. }
  141.  
  142. int size_of_hashtable()
  143. {
  144.     return size;
  145. }
  146.  
  147. void main()
  148. {
  149. 	int choice, key, value, n, c;
  150. 	clrscr();
  151.  
  152. 	array = (struct hashtable_item*) malloc(max * sizeof(struct hashtable_item*));
  153. 	init_array();
  154.  
  155. 	do {
  156. 		printf("Implementation of Hash Table in C with Linear Probing \n\n");
  157. 		printf("MENU-: \n1.Inserting item in the Hashtable" 
  158.                               "\n2.Removing item from the Hashtable" 
  159.                               "\n3.Check the size of Hashtable"
  160.                               "\n4.Display Hashtable"
  161. 		       "\n\n Please enter your choice-:");
  162.  
  163. 		scanf("%d", &choice);
  164.  
  165. 		switch(choice) 
  166.                 {
  167.  
  168. 		case 1:
  169.  
  170. 		      printf("Inserting element in Hashtable\n");
  171. 		      printf("Enter key and value-:\t");
  172. 		      scanf("%d %d", &key, &value);
  173. 		      insert(key, value);
  174.  
  175. 		      break;
  176.  
  177. 		case 2:
  178.  
  179. 		      printf("Deleting in Hashtable \n Enter the key to delete-:");
  180. 		      scanf("%d", &key);
  181. 		      remove_element(key);
  182.  
  183. 		      break;
  184.  
  185. 		case 3:
  186.  
  187. 		      n = size_of_hashtable();
  188. 		      printf("Size of Hashtable is-:%d\n", n);
  189.  
  190. 		      break;
  191.  
  192. 		case 4:
  193.  
  194. 		      display();
  195.  
  196. 		      break;
  197.  
  198. 		default:
  199.  
  200. 		       printf("Wrong Input\n");
  201.  
  202. 		}
  203.  
  204. 		printf("\n Do you want to continue-:(press 1 for yes)\t");
  205. 		scanf("%d", &c);
  206.  
  207. 	}while(c == 1);
  208.  
  209. 	getch();
  210.  
  211. }
Program Explanation

1. Create a structure, item having a key and value representing data to be inserted in hash table.
2. Create another structure, hash table_item with variable data (key and value) and flag as a status variable which informs about the status of array index.
flag = 1 : presence of some data at the array index.
flag = 0 : data not present in array index even once
flag = 2 : data had been removed from array index at least once
3. Now create an array of structure (hashtable_item) of some certain size (10, in this case). This array will be our hash table.
4. A menu is displayed on the screen.
5. User must choose one option from four choices given in the menu.
6. 1st choice: Inserting item into hash table
(a) Take a key and a value as input.
(b) Calculate index as per the given key (using hashcode() function).
(c) Access the element at this calculated index in array.
(d) If there is no element at that particular array index, add straight way.
(e) If an element is present, check whether the given key matches the element’s key. If yes, then update it’s value and return. Otherwise probe through subsequent elements (looping back if necessary), to find free space. While probing
* if given key matches the element’s key, update its value and return.
* if a free space is found, add the data at that position.
Probing will stop until we reach the same element from where we began probing. Until then, if no free space is found, then add will fail.
7. 2nd choice: Removing a key from hash table
(a) Take a key as input which needs to be removed.
(b) Calculate index as per the given key (using hashcode() function).
(c) Access the element at the calculated array index.
(d) If an element is present, check whether the given key matches the element’s key. If yes, then delete the key and return decrementing the size. Otherwise probe through subsequent elements (looping back if necessary), to find free space with flag = 0. While probing
* if given key matches the element’s key, delete and return.
* if a free space is found (with flag = 2), continue to probe.
(e) If no free space (flag = 0) is found even after probing through all element it means, key does not exist in the hash table.
8. 3rd choice: Size of hash table
(a) Each time we add a new data item into the hash table, we increment it’s size by 1.
(b) Each time we remove a data item from the hash table, we decrement it’s size by 1.
(c) The size of the hash table can be determined either by size variable or size_of_hashtable() method.

advertisement
advertisement

9. 4th choice: Display hash table
(a) Function display() runs for displaying hash table contents.
(b) Here a for loop runs from 0 to array_size-1 with i as iterator.
(c) The code inside loop consists of taking i as index and accessing each element at that index of array.

Runtime Test Cases
 
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 3
Size of Hashtable is-: 0
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 1
Inserting element in Hashtable
Enter key and value-:   12 	10
 
 Key (12) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 1
Inserting element in Hash table
Enter key and value-:   122 	4
 
 Key (122) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 3
Size of Hashtable is-: 2
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 4
Array[0] has  no elements
 
Array[1] has no elements
 
Array[2] has elements-:
12 (key) and 10 (value)
 
Array[3] has elements-:
122(key) and 5(value)
 
Array[4] has no elements
 
Array[5] has no elements
 
Array[6] has no elements
 
Array[7] has no elements
 
Array[8] has no elements
 
Array[9] has no elements
 
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 2
Deleting in Hashtable
Enter the key to delete-: 122
 
 Key (122) has been removed
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Linear Probing
MENU-:
1. Inserting item in the Hashtable
2. Removing item from the Hashtable
3. Check the size of Hashtable
4. Display Hashtable
 
Please enter your choice-: 2
Deleting in Hashtable
Enter the key to delete-: 56
 
 This key does not exist
 
Do you want to continue-:(press 1 for yes) 2

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.