Hash Table in C with collision Handling: Insertion, deletion, retrieval
2. Collision Resolution Extension Challenges
Implement a basic hash table in C with functions for insertion, deletion, and retrieval of key-value pairs. Write a C program that extends the above basic hash table implementation to handle collisions using techniques such as chaining or open addressing.
Sample Solution:
C Code:
// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Structure to represent a key-value pair
struct KeyValuePair {
char key[50];
int value;
struct KeyValuePair* next;
};
// Structure to represent a hash table
struct HashTable {
int size;
struct KeyValuePair** table;
};
// Function to create a new key-value pair
struct KeyValuePair* createKeyValuePair(const char* key, int value) {
struct KeyValuePair* newPair = (struct KeyValuePair*)malloc(sizeof(struct KeyValuePair));
if (newPair != NULL) {
strcpy(newPair->key, key);
newPair->value = value;
newPair->next = NULL;
}
return newPair;
}
// Function to create a new hash table
struct HashTable* createHashTable(int size) {
struct HashTable* newTable = (struct HashTable*)malloc(sizeof(struct HashTable));
if (newTable != NULL) {
newTable->size = size;
newTable->table = (struct KeyValuePair**)calloc(size, sizeof(struct KeyValuePair*));
}
return newTable;
}
// Hash function to calculate the index
unsigned int hashFunction(const char* key, int tableSize) {
unsigned int hash = 0;
while (*key) {
hash = (hash << 5) + *key++;
}
return hash % tableSize;
}
// Function to insert a key-value pair into the hash table
void insert(struct HashTable* hashTable, const char* key, int value) {
unsigned int index = hashFunction(key, hashTable->size);
// Create a new key-value pair
struct KeyValuePair* newPair = createKeyValuePair(key, value);
// Insert the new pair at the beginning of the linked list
newPair->next = hashTable->table[index];
hashTable->table[index] = newPair;
}
// Function to retrieve the value associated with a key
int retrieve(struct HashTable* hashTable, const char* key) {
unsigned int index = hashFunction(key, hashTable->size);
struct KeyValuePair* current = hashTable->table[index];
// Traverse the linked list at the index
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value; // Key found, return the value
}
current = current->next;
}
return -1; // Key not found
}
// Function to remove a key-value pair from the hash table
void removeKey(struct HashTable* hashTable, const char* key) {
unsigned int index = hashFunction(key, hashTable->size);
struct KeyValuePair* current = hashTable->table[index];
struct KeyValuePair* previous = NULL;
// Traverse the linked list at the index
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
if (previous == NULL) {
hashTable->table[index] = current->next; // Update head if it's the first node
} else {
previous->next = current->next; // Update pointers to remove the current node
}
free(current); // Free memory for the removed node
return;
}
previous = current;
current = current->next;
}
}
// Function to display the contents of the hash table
void displayHashTable(struct HashTable* hashTable) {
for (int i = 0; i < hashTable->size; i++) {
printf("[%d] -> ", i);
struct KeyValuePair* current = hashTable->table[i];
while (current != NULL) {
printf("(%s, %d) -> ", current->key, current->value);
current = current->next;
}
printf("NULL\n");
}
}
// Function to free the memory allocated for the hash table
void freeHashTable(struct HashTable* hashTable) {
for (int i = 0; i < hashTable->size; i++) {
struct KeyValuePair* current = hashTable->table[i];
while (current != NULL) {
struct KeyValuePair* temp = current;
current = current->next;
free(temp);
}
}
free(hashTable->table);
free(hashTable);
}
// Main function
int main() {
struct HashTable* hashTable = createHashTable(10);
// Insert key-value pairs
insert(hashTable, "Endymion", 35);
insert(hashTable, "Clover", 38);
insert(hashTable, "Khazhak", 35);
insert(hashTable, "Melcha", 41);
insert(hashTable, "Taqqiq", 42); // Collision with "Endymion"
insert(hashTable, "Ufuoma", 55); // Collision with "Khazhak"
printf("Initial Hash Table:\n");
displayHashTable(hashTable);
printf("\n");
// Retrieve and print values for specific keys
printf("Value for key 'Endymion': %d\n", retrieve(hashTable, "Endymion"));
printf("Value for key 'Taqqiq': %d\n", retrieve(hashTable, "Taqqiq"));
printf("Value for key 'Faustus': %d\n", retrieve(hashTable, "Faustus"));
printf("\n");
// Remove a key-value pair
printf("Deleting key 'Clover'\n");
removeKey(hashTable, "Clover");
displayHashTable(hashTable);
printf("\n");
// Free allocated memory
freeHashTable(hashTable);
return 0;
}
Output:
Initial Hash Table: [0] -> NULL [1] -> NULL [2] -> (Endymion, 35) -> NULL [3] -> NULL [4] -> NULL [5] -> (Melcha, 41) -> NULL [6] -> NULL [7] -> (Ufuoma, 55) -> NULL [8] -> (Clover, 38) -> NULL [9] -> (Taqqiq, 42) -> (Khazhak, 35) -> NULL Value for key 'Endymion': 35 Value for key 'Taqqiq': 42 Value for key 'Faustus': -1 Deleting key 'Clover' [0] -> NULL [1] -> NULL [2] -> (Endymion, 35) -> NULL [3] -> NULL [4] -> NULL [5] -> (Melcha, 41) -> NULL [6] -> NULL [7] -> (Ufuoma, 55) -> NULL [8] -> NULL [9] -> (Taqqiq, 42) -> (Khazhak, 35) -> NULL
Explanation:
In the exercise above,
- Structures:
- KeyValuePair: Represents a key-value pair with a key (string), value (integer), and a pointer to the next KeyValuePair (for handling collisions).
- HashTable: Represents a hash table with a specified size and an array of pointers to KeyValuePairs.
- Functions:
- createKeyValuePair: Creates a new key-value pair and initializes its members.
- createHashTable: Creates a new hash table and allocates memory for the array of pointers.
- hashFunction: Calculates the index for a key using a simple hash function.
- insert: Inserts a key-value pair into the hash table, handling collisions using chaining.
- retrieve: Retrieves the value associated with a given key from the hash table.
- removeKey: Removes a key-value pair from the hash table.
- displayHashTable: Displays the contents of the hash table, including linked lists for collisions.
- freeHashTable: Frees the memory allocated for the hash table.
- Main Function:
- Creates a hash table with a size of 10.
- Inserts several key-value pairs into the hash table, intentionally causing collisions.
- Displays the initial state of the hash table.
- Retrieves and prints values for specific keys.
- Deletes a key-value pair.
- Displays the updated hash table.
- Frees allocated memory.
Flowchart:
For more Practice: Solve these Related Problems:
- Write a C program to implement a hash table using chaining with doubly linked lists to allow bidirectional traversal of collisions.
- Write a C program to implement a hash table using quadratic probing and demonstrate how it minimizes clustering.
- Write a C program to implement a hash table using cuckoo hashing for collision resolution.
- Write a C program to compare the performance of chaining versus open addressing techniques by tracking probe counts.
Go to:
PREV : Basic Hash Table Extended Challenges.
NEXT : String Hash Function Challenges.
C Programming Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.