Hash tables with quadratic probing are employed in this C code. An associative array, a data structure that facilitates the mapping of keys to values, is established through a structure known as a hash table. This hash table utilizes a hash function to generate an index within an array of slots or buckets. Similar to linear probing, quadratic probing involves inspecting elements at increasing squares of offsets (1^2=1, 2^2=4, 3^2=9, 4^2=16, etc.) when trying to insert into an occupied slot.
Solution for the problem:
- Make a hash table or an array of structures.
- Take as input a key and a value that will be saved in a hash table .
- An index will be generated that corresponds to the key; each key is put in a specific array index .
- Access the data contained in that array index using the produced index.
- If there are no data, construct one, add the data item (key and value), and increase the hash table's size.
- If the data is present, look for a blank space in the following items (looping back if necessary) to insert the new data item.
Note:
In this scenario, rather than employing Linear Probing, probing will be executed utilizing the subsequent formula:
The formula (currentPosition + h) % arraySize is commonly used for implementing Linear Probing in hash tables.
The formula (currentPosition + (h * h)) % arraySize is commonly used for implementing Quadratic Probing in hash tables.
Where h = 1, 2, 3, 4 , and so on.
- A for loop is used to access an element at each index to display all of the hash table's elements .
- To remove a key from a hash table , we must first determine its index and then delete it if the key matches. If not, we must search through the elements until we discover the key or an empty area where no data has been input, which denotes that the hash table has no data.
- Exit.
Program for the quadratic probing:
Let's consider an example to grasp the application of quadratic probing in the C programming language.
Example
#include <stdio.h>
#include <stdlib.h>
struct item {
int key;
int value;
};
struct hashtable_item {
int flag;
struct item *data;
};
struct hashtable_item *array;
int size = 0;
int max = 10;
int hashcode(int key) {
return key % max;
}
void init_array() {
array = (struct hashtable_item*) malloc(max * sizeof(struct hashtable_item));
for (int i = 0; i < max; i++) {
array[i].flag = 0;
array[i].data = NULL;
}
}
void insert(int key, int value) {
int index = hashcode(key);
int i = index;
int h = 1;
struct item *new_item = (struct item*) malloc(sizeof(struct item));
new_item->key = key;
new_item->value = value;
while (array[i].flag == 1) {
if (array[i].data->key == key) {
printf("\nThis key is already present in the hash table, updating its value\n");
array[i].data->value = value;
return;
}
i = (i + (h * h)) % max;
h++;
if (i == index) {
printf("\nHash table is full, cannot add more elements\n");
return;
}
}
array[i].flag = 1;
array[i].data = new_item;
printf("\nKey (%d) has been inserted\n", key);
size++;
}
void remove_element(int key) {
int index = hashcode(key);
int i = index;
int h = 1;
while (array[i].flag != 0) {
if (array[i].flag == 1 && array[i].data->key == key) {
array[i].flag = 2;
free(array[i].data); // Free memory for the removed item
array[i].data = NULL;
size--;
printf("\nKey (%d) has been removed\n", key);
return;
}
i = (i + (h * h)) % max;
h++;
if (i == index) {
break;
}
}
printf("\nKey does not exist\n");
}
void display() {
for (int i = 0; i < max; i++) {
if (array[i].flag != 1) {
printf("\nArray[%d] has no elements\n", i);
} else {
printf("\nArray[%d] has elements\n%d (key) and %d (value)\n", i, array[i].data->key, array[i].data->value);
}
}
}
int size_of_hashtable() {
return size;
}
int main() {
int choice, key, value, n, c;
init_array();
do {
printf("Implementation of Hash Table in C with Quadratic Probing.\n\n");
printf("MENU-:\n1.Insert item in the Hash table\n2.Remove item from the Hash table\n3.Check the size of Hash table\n4.Display Hash table\n5.Exit\n\nPlease enter your choice-:");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Inserting element in Hash table\nEnter key and value:\t");
scanf("%d %d", &key, &value);
insert(key, value);
break;
case 2:
printf("Deleting in Hash table\nEnter the key to delete:");
scanf("%d", &key);
remove_element(key);
break;
case 3:
n = size_of_hashtable();
printf("Size of Hash table is:%d\n", n);
break;
case 4:
display();
break;
case 5:
printf("Exiting...\n");
break;
default:
printf("Wrong Input\n");
}
if (choice != 5) {
printf("\nDo you want to continue? (Press 1 for yes):");
scanf("%d", &c);
} else {
c = 0;
}
} while (c == 1);
// Free allocated memory
for (int i = 0; i < max; i++) {
if (array[i].flag == 1) {
free(array[i].data);
}
}
free(array);
return 0;
}
Output:
Runtime test cases:
Example
1. Inserting and Displaying Elements
Implementation of Hash Table in C with Quadratic Probing.
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 5 25
Key (5) has been inserted
Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 15 225
Key (15) has been inserted
Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 4
Array[0] has no elements
Array[1] has no elements
Array[2] has no elements
Array[3] has no elements
Array[4] has no elements
Array[5] has elements
5 (key) and 25 (value)
Array[6] has no elements
Array[7] has no elements
Array[8] has no elements
Array[9] has elements
15 (key) and 225 (value)
Do you want to continue? (Press 1 for yes): 0
2. removing an element
Implementation of Hash Table in C with Quadratic Probing.
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 5 25
Key (5) has been inserted
Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 2
Deleting in Hash table
Enter the key to delete: 5
Key (5) has been removed
Do you want to continue? (Press 1 for yes): 0
3. Checking Hash Table Size
Implementation of Hash Table in C with Quadratic Probing.
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 5 25
Key (5) has been inserted
Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit
Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 15 225
Key (15) has been inserted
Do you want to continue? (Press 1 for yes): 1
MENU-:
1. Insert item in the Hash table
2. Remove item from the Hash table
3. Check the size of Hash table
4. Display Hash table
5. Exit
Please enter your choice-: 3
Size of Hash table is: 2
Do you want to continue? (Press 1 for yes): 0
Explanation:
- In this example, the program defines two structures: struct hashtable_item to represent objects in the hash table and struct item to hold key-value pairs. Array , a pointer to the hash table, size to keep track of the number of entries, and max for hash table size are examples of global variables .
- The hashcode function determines the hash index by performing a modulo operation on the key. This index determines the position of an item in the array of the hash table.
- The hash table array is initialized by the init_array All flags are set to 0 (which denotes an empty slot), and data pointers are set to NULL .
- The insert operation increases the hash table's inventory. The hash function is used to determine the index , and quadratic probing (growing by squared values of h) is used to locate an open slot . A new item is inserted if the slot is vacant. The value is updated if the key already exists. A suitable message is presented if the hash table is full.
- The hash table's contents are removed using the remove_element It uses the hash function to determine the index and quadratic probing to determine the location of the key. If the key is discovered, the object is eliminated by altering the size , changing the flag , and freeing up memory . The proper notifications are presented if the table is full or the key doesn't exist.
- The display function does print if each slot has elements after iterating through the hash table array. If an element is present, its key and value are printed.
- The sizeofhashtable function returns the hash table's current size (the number of currently stored elements).
- The hash table is initialized by the main function using the init_array . The user is presented with a menu that includes choices to add and remove items, verify the size, see the hash table , and exit . The user is given the option to continue or quit when the relevant function is run based on their selection. Memory is set aside for items, and the array is released after the user logs out.