C Program to Implement Hash Tables chaining with Singly Linked Lists

«
»

This is a C Program to Implement a Hash Table using Singly Linked List.

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. This program will implement hash table where at each array index, we will create a Linked List, to prevent key collision. Key having same index will be stored in Linked List as it can store multiple data.

Problem Solution

1. Create an array of Linked List (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 Linked List of a particular array index.
4. Using the generated index, extract the Linked List located in that array index.
5. In case of absence of a Linked List, create one and insert a data item(key and value) into it and increment the size of hash table.
6. In case the list already exists, search for the key (given as input) in the Linked List, and add the data item (key and value) at the end of list if key does not belong to the list and increment the size, otherwise update the value of given (and already present) key in the Linked List.
7. To display all the elements of hash table, Linked List at each index is extracted and elements(key and value) are read until we reach at its end.
8. To remove a key from hash table, we will first calculate its index and extract its Linked List, find the key in list and remove it if it is present.
9. Exit

advertisement
Program/Source Code

Here is the source code of the C Program to Implement a Hash Table chaining with Singly Linked List. 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. #include<conio.h>
  4.  
  5. /* Node for storing an item in a Linked List */
  6. struct node 
  7. {
  8. 	int key;
  9. 	int value;
  10. 	struct node *next;
  11. };
  12.  
  13. /* For storing a Linked List at each index of Hash Table  */
  14. struct arrayitem 
  15. {
  16.  
  17. 	struct node *head;   
  18. 	/* head pointing the first element of Linked List at an index of Hash Table */
  19.  
  20. 	struct node *tail;   
  21. 	/* tail pointing the last element of Linked List at an index of Hash Table */
  22.  
  23. };
  24.  
  25. struct arrayitem *array;
  26. int size = 0;         /* Determines the no. of elements present in Hash Table */
  27. int max = 10;	      /* Determines the maximum capacity of Hash Table array */
  28.  
  29. /* This function creates an index corresponding to the every given key */
  30. int hashcode(int key)
  31. {
  32. 	return (key % max);
  33. }
  34.  
  35. struct node* get_element(struct node *list, int find_index);
  36. void remove_element(int key);
  37. void rehash();
  38. void init_array();
  39.  
  40. void insert(int key, int value)
  41. {
  42.   	float n = 0.0;     
  43. 	/* n => Load Factor, keeps check on whether rehashing is required or not */
  44.  
  45. 	int index = hashcode(key);  
  46.  
  47. 	/* Extracting Linked List at a given index */
  48. 	struct node *list = (struct node*) array[index].head;
  49.  
  50. 	/* Creating an item to insert in the Hash Table */
  51. 	struct node *item = (struct node*) malloc(sizeof(struct node));
  52. 	item->key = key;
  53. 	item->value = value;
  54. 	item->next = NULL;
  55.  
  56. 	if (list == NULL) 
  57.         {
  58. 		/* Absence of Linked List at a given Index of Hash Table */
  59.  
  60. 		printf("Inserting %d(key) and %d(value) \n", key, value);
  61. 		array[index].head = item;
  62. 		array[index].tail = item;
  63. 		size++;
  64.  
  65. 	}
  66.         else 
  67.         {
  68. 		/* A Linked List is present at given index of Hash Table */
  69.  
  70. 		int find_index = find(list, key); 
  71. 		if (find_index == -1) 
  72.                 {
  73. 			/*
  74. 			 *Key not found in existing linked list
  75. 			 *Adding the key at the end of the linked list
  76. 			*/
  77.  
  78. 			array[index].tail->next = item;
  79. 			array[index].tail = item;
  80. 			size++;
  81.  
  82. 		}else 
  83.                  {
  84. 			/*
  85. 			 *Key already present in linked list
  86. 			 *Updating the value of already existing key
  87. 			*/
  88.  
  89. 			struct node *element = get_element(list, find_index);
  90. 			element->value = value;
  91.  
  92. 		}
  93.  
  94. 	}
  95.  
  96. 	//Calculating Load factor
  97. 	n = (1.0 * size) / max;
  98. 	if (n >= 0.75) 
  99.         {
  100. 		//rehashing
  101.  
  102. 		printf("going to rehash\n");
  103. 		rehash();
  104.  
  105. 	}
  106.  
  107. }
  108.  
  109. void rehash()
  110. {
  111. 	struct arrayitem *temp = array;     
  112. 	/* temp pointing to the current Hash Table array */
  113.  
  114. 	int i = 0, n = max;
  115. 	size = 0;
  116. 	max = 2 * max;
  117.  
  118. 	/*
  119. 	 *array variable is assigned with newly created Hash Table
  120. 	 *with double of previous array size
  121. 	*/
  122. 	array = (struct arrayitem*) malloc(max * sizeof(struct node));
  123. 	init_array();
  124.  
  125. 	for (i = 0; i < n; i++) 
  126.         {
  127.  
  128. 		/* Extracting the Linked List at position i of Hash Table array */
  129.  		struct node* list = (struct node*) temp[i].head;
  130.  
  131. 		if (list == NULL) 
  132.                 {
  133.  
  134. 			/* if there is no Linked List, then continue */
  135. 			continue;
  136.  
  137. 		}
  138.                 else 
  139.                 {
  140. 			/*
  141. 			 *Presence of Linked List at i
  142. 			 *Keep moving and accessing the Linked List item until the end.
  143. 			 *Get one key and value at a time and add it to new Hash Table array.
  144. 			*/
  145.  
  146. 			while (list != NULL) 
  147.                         {
  148. 				insert(list->key, list->value);
  149. 				list = list->next;
  150. 			}
  151.  
  152. 		}
  153.  
  154. 	}
  155. 	temp = NULL;
  156. }
  157.  
  158. /*
  159.  *This function finds the given key in the Linked List
  160.  *Returns it's index
  161.  *Returns -1 in case key is not present
  162. */
  163. int find(struct node *list, int key)
  164. {
  165. 	int retval = 0;
  166. 	struct node *temp = list;
  167. 	while (temp != NULL) 
  168.         {
  169. 		if (temp->key == key)
  170.                 {
  171. 			return retval;
  172. 		}
  173.   		temp = temp->next;
  174. 		retval++;
  175. 	}
  176. 	return -1;
  177.  
  178. }
  179.  
  180. /* Returns the node (Linked List item) located at given find_index  */
  181. struct node* get_element(struct node *list, int find_index)
  182. {
  183. 	int i = 0;
  184. 	struct node *temp = list;
  185. 	while (i != find_index) 
  186.         {
  187. 		temp = temp->next;
  188. 		i++;
  189. 	}
  190. 	return temp;
  191. }
  192.  
  193. /* To remove an element from Hash Table */ 
  194. void remove_element(int key)
  195. {
  196. 	int index = hashcode(key);
  197. 	struct node *list = (struct node*) array[index].head;
  198.  
  199. 	if (list == NULL) 
  200.         {
  201. 		printf("This key does not exists\n");
  202.  
  203. 	}
  204.         else 
  205.         {
  206. 		int find_index = find(list, key);
  207.  
  208. 		if (find_index == -1) 
  209.                 {
  210. 			printf("This key does not exists\n");
  211.  
  212. 		}
  213.                 else 
  214.                 {
  215.  			struct node *temp = list;
  216. 			if (temp->key == key) 
  217.                         {
  218.  
  219.   				array[index].head = temp->next;
  220. 				printf("This key has been removed\n");
  221. 				return;
  222. 			}
  223.  
  224. 			while (temp->next->key != key) 
  225.                         {
  226.  				temp = temp->next;
  227. 			}
  228.  
  229.   			if (array[index].tail == temp->next) 
  230.                         {
  231. 				temp->next = NULL;
  232. 				array[index].tail = temp;
  233.  
  234. 			}
  235.                         else 
  236.                         {
  237. 				temp->next = temp->next->next;
  238.  
  239. 			}
  240.  
  241. 			printf("This key has been removed\n");
  242.  
  243. 		}
  244.  
  245. 	}
  246.  
  247. }
  248.  
  249. /* To display the contents of Hash Table */
  250. void display()
  251. {
  252. 	int i = 0;
  253. 	for (i = 0; i < max; i++) 
  254.         {
  255. 		struct node *temp = array[i].head;
  256. 		if (temp == NULL) 
  257.                 {
  258. 			printf("array[%d] has no elements\n", i);
  259.  
  260. 		}
  261.                 else 
  262.                 {
  263. 			printf("array[%d] has elements-: ", i);
  264. 			while (temp != NULL)
  265.                         {
  266. 				printf("key= %d  value= %d\t", temp->key, temp->value);
  267. 				temp = temp->next;
  268. 			}
  269. 			printf("\n");
  270.  
  271. 		}
  272. 	}
  273. }
  274.  
  275. /* For initializing the Hash Table */
  276. void init_array()
  277. {
  278. 	int i = 0;
  279. 	for (i = 0; i < max; i++)
  280.         {
  281. 		array[i].head = NULL;
  282. 		array[i].tail = NULL;
  283. 	}
  284.  
  285. }
  286.  
  287. /* Returns size of Hash Table */ 
  288. int size_of_array()
  289. {
  290. 	return size;
  291. }
  292.  
  293. void main() 
  294. {
  295. 	int choice, key, value, n, c;
  296. 	clrscr();
  297.  
  298. 	array = (struct arrayitem*) malloc(max * sizeof(struct arrayitem*));
  299. 	init_array();
  300.  
  301. 	do {
  302. 		printf("Implementation of Hash Table in C chaining with Singly Linked List \n\n");
  303. 		printf("MENU-: \n1.Inserting item in the Hash Table"
  304.                               "\n2.Removing item from the Hash Table"
  305.                               "\n3.Check the size of Hash Table" 
  306.                               "\n4.To display a Hash Table"
  307. 		       "\n\n Please enter your choice -: ");
  308.  
  309.  		scanf("%d", &choice);
  310.  
  311. 		switch(choice) 
  312.                 {
  313.  
  314. 		case 1:
  315.  
  316. 		      printf("Inserting element in Hash Table\n");
  317. 		      printf("Enter key and value-:\t");
  318. 		      scanf("%d %d", &key, &value);
  319. 		      insert(key, value);
  320.  
  321. 		      break;
  322.  
  323. 		case 2:
  324.  
  325. 		      printf("Deleting in Hash Table \nEnter the key to delete-:");
  326. 		      scanf("%d", &key);
  327. 		      remove_element(key);
  328.  
  329. 		      break;
  330.  
  331. 		case 3:
  332.  
  333. 		      n = size_of_array();
  334. 		      printf("Size of Hash Table is-:%d\n", n);
  335.  
  336. 		      break;
  337.  
  338. 		case 4:
  339.  
  340. 		      display();
  341.  
  342. 		      break;
  343.  
  344. 		default:
  345.  
  346. 		       printf("Wrong Input\n");
  347.  
  348. 		}
  349.  
  350. 		printf("\nDo you want to continue-:(press 1 for yes)\t");
  351. 		scanf("%d", &c);
  352.  
  353. 	}while(c == 1);
  354.  
  355. 	getch();
  356.  
  357. }
Program Explanation

1. Create a structure, node (Linked List item) with key and value as data and next as a pointer variable which points the structure element of node type.
2. Create another structure, arrayitem (for Linked List) with head having the address of first element of Linked List and tail having the address of last element of Linked List.
3. Now create an array of Linked List of some certain size (10, in this case).
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.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, check whether the key already present in it by finding the location of key using find() method which returns -1 if key is not present. In that case, we will create a data item and add it to the end of Linked List. If key is already present in the list, we will get its location index and extract the element using get_element() function and update its value.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, then create a data item and a Linked List and add the data item to it.
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.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, find the location index of the key in Linked List using find() method which returns -1 if key not present. The key is removed using remove() method if it is present otherwise ‘Key not present’ message will get displayed.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, therefore no deletion is required.
8. 3rd choice: Size of hash table
(a) Each time we add a new data item into the hash table, we increment its size by 1.
(b) 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 locating each Linked List at that index of array.
(d) As the content of each node of Linked List is displayed the next variable (pointer)
is used to proceed further until the end of list is reached.

Runtime Test Cases
Implementation of Hash Table in C chaining with Singly Linked List
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display a Hash Table
 
Please enter your choice-: 3
Size of Hash Table is-: 0
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Singly Linked List
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display a Hash Table
 
Please enter your choice-: 1
Inserting element in Hash Table
Enter key and value-:   1 	10
Inserting 1(key) and 10(value)
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Singly Linked List
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display a Hash Table
 
Please enter your choice-: 4
array[0] has elements-:		key=1  value=10
array[1] has no elements
array[2] has no elements
array[3] has no elements
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 chaining with Singly Linked List
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display a Hash Table
 
Please enter your choice-: 2
Deleting key from Hash Table
Enter the key to delete-: 3
Element does not exists.
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Singly Linked List
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display a Hash Table
 
Please enter your choice-: 2
Deleting key from Hash Table
Enter the key to delete-: 1
Key 1 deleted.
 
Do you want to continue-:(press 1 for yes) 2

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter