C Program to Implement Hash Tables

«
»

This is a C Program to Implement Hash Tables.

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 a hash table by putting each element in a particular index of hash table array.

Problem Solution

1. Create an array of structure, data (i.e a hash table).
2. Take a key to be stored in hash table as input.
3. Corresponding to the key, an index will be generated.
4. In case of absence of data in that index of array, create one and insert the data item (key and value) into it and increment the size of hash table.
5. In case the data already exists, the new data cannot be inserted if the already present data does not match given key.
6. To display all the elements of hash table, data at each index is extracted and elements (key and value) are read and printed.
7. To remove a key from hash table, we will first calculate its index and extract its data, delete the key in case it matches the given key.
8. Exit

advertisement
Program/Source Code

Here is the source code of the C Program to implement a hash table. 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. struct data 
  5. {
  6. 	int key;
  7. 	int value;
  8. };
  9.  
  10. struct data *array;
  11. int capacity = 10;
  12. int size = 0;
  13.  
  14. /* this function gives a unique hash code to the given key */
  15. int hashcode(int key)
  16. {
  17. 	return (key % capacity);
  18. }
  19.  
  20. /* it returns prime number just greater than array capacity */
  21. int get_prime(int n)
  22. {
  23. 	if (n % 2 == 0) 
  24.         {
  25. 		n++;
  26. 	}
  27. 	for (; !if_prime(n); n += 2);
  28.  
  29. 	return n;
  30. }
  31.  
  32. /* to check if given input (i.e n) is prime or not */
  33. int if_prime(int n)
  34. {
  35. 	int i;
  36. 	if ( n == 1  ||  n == 0) 
  37.         {
  38. 		return 0;
  39. 	}
  40. 	for (i = 2; i < n; i++) 
  41.         {
  42. 		if (n % i == 0) 
  43.                 {
  44. 			return 0;
  45. 		}
  46. 	}
  47. 	return 1;
  48. }
  49.  
  50. void init_array()
  51. {
  52. 	int i;
  53. 	capacity = get_prime(capacity);
  54. 	array = (struct data*) malloc(capacity * sizeof(struct data));
  55. 	for (i = 0; i < capacity; i++) 
  56.         {
  57. 		array[i].key = 0;
  58. 		array[i].value = 0;
  59. 	}
  60. }
  61.  
  62. /* to insert a key in the hash table */
  63. void insert(int key)
  64. {
  65. 	int index = hashcode(key);
  66. 	if (array[index].value == 0) 
  67.         {
  68. 		/*  key not present, insert it  */
  69. 		array[index].key = key;
  70. 		array[index].value = 1;
  71. 		size++;
  72. 		printf("\n Key (%d) has been inserted \n", key);
  73. 	}
  74. 	else if(array[index].key == key) 
  75.         {
  76. 		/*  updating already existing key  */
  77. 		printf("\n Key (%d) already present, hence updating its value \n", key);
  78. 		array[index].value += 1;
  79. 	}
  80. 	else
  81.         {
  82. 		/*  key cannot be insert as the index is already containing some other key  */
  83. 		printf("\n ELEMENT CANNOT BE INSERTED \n");
  84. 	}
  85. }
  86.  
  87. /* to remove a key from hash table */
  88. void remove_element(int key)
  89. {
  90. 	int index  = hashcode(key);
  91. 	if(array[index].value == 0)
  92.         {
  93. 		printf("\n This key does not exist \n");
  94. 	}
  95. 	else {
  96. 		array[index].key = 0;
  97. 		array[index].value = 0;
  98. 		size--;
  99. 		printf("\n Key (%d) has been removed \n", key);
  100. 	}
  101. }
  102.  
  103. /* to display all the elements of a hash table */
  104. void display()
  105. {
  106. 	int i;
  107. 	for (i = 0; i < capacity; i++)
  108.         {
  109. 		if (array[i].value == 0)
  110.                 {
  111. 			printf("\n Array[%d] has no elements \n");
  112. 		}
  113. 		else 
  114.                 {
  115. 			printf("\n array[%d] has elements -:\n key(%d) and value(%d) \t", i, array[i].key, array[i].value);
  116. 		}
  117. 	}
  118. }
  119.  
  120. int size_of_hashtable()
  121. {
  122. 	return size;
  123. }
  124.  
  125. void main()
  126. {
  127. 	int choice, key, value, n, c;
  128. 	clrscr();
  129.  
  130. 	init_array();
  131.  
  132. 	do {
  133. 		printf("\n Implementation of Hash Table in C \n\n");
  134. 		printf("MENU-:  \n1.Inserting item in the Hash Table" 
  135.                                "\n2.Removing item from the Hash Table"
  136. 		               "\n3.Check the size of Hash Table" 
  137.                                "\n4.Display a Hash Table"
  138. 		       "\n\n Please enter your choice -:");
  139.  
  140. 		scanf("%d", &choice);
  141.  
  142. 		switch(choice) 
  143.                 {
  144.  
  145. 		case 1:
  146.  
  147. 		      printf("Inserting element in Hash Table\n");
  148. 		      printf("Enter key -:\t");
  149. 		      scanf("%d", &key);
  150. 		      insert(key);
  151.  
  152. 		      break;
  153.  
  154. 		case 2:
  155.  
  156. 		      printf("Deleting in Hash Table \n Enter the key to delete-:");
  157. 		      scanf("%d", &key);
  158. 		      remove_element(key);
  159.  
  160. 		      break;
  161.  
  162. 		case 3:
  163.  
  164. 		      n = size_of_hashtable();
  165. 		      printf("Size of Hash Table is-:%d\n", n);
  166.  
  167. 		      break;
  168.  
  169. 		case 4:
  170.  
  171. 		      display();
  172.  
  173. 		      break;
  174.  
  175. 		default:
  176.  
  177. 		       printf("Wrong Input\n");
  178.  
  179. 		}
  180.  
  181. 		printf("\n Do you want to continue-:(press 1 for yes)\t");
  182. 		scanf("%d", &c);
  183.  
  184. 	}while(c == 1);
  185.  
  186. 	getch();
  187.  
  188. }
Program Explanation

1. Create a structure, data (hash table item) with key and value as data.
2. Now create an array of structure, data of some certain size (10, in this case). But, the size of array must be immediately updated to a prime number just greater than initial array capacity (i.e 10, in this case).
3. A menu is displayed on the screen.
4. User must choose one option from four choices given in the menu.
5. 1st choice: Inserting item into hash table
(a) Take a key as input.
(b) Calculate index as per the given key.
(c) Locate the calculated array index.
(d) If some data is present, check whether the key matches the already present data key. If it does, then its value is updated. If not, then the new data cannot be inserted.
6. 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 data at the calculated array index.
(d) If some data is already present, check whether the key matches the already present data key. If it does, then this key gets deleted. If not, this means data does not exists.
7. 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.
8. 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 data item at that index of array.

advertisement
Runtime Test Cases
 
Implementation of Hash Table in C 
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display 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 
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 1
Inserting element in Hash Table
Enter key -:   1 	
 
 key (1) and value (1) has been inserted
 
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 Hash Table
 
Please enter your choice-: 4
array[0] has no elements		
array[1] has no elements	key = 1 and value = 1
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 
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 2
Deleting key from Hash Table
Enter the key to delete-: 3
 
 This key does not exist.
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C 
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 2
Deleting key from Hash Table
Enter the key to delete-: 1
 
 Key 1 has been removed.
 
Do you want to continue-:(press 1 for yes) 2

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

advertisement

advertisement
advertisement
advertisement
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