Basic Hash table implementation in C: Insertion, deletion, and retrieval
Write a C program that implements a basic hash table with functions for insertion, deletion, and retrieval of key-value pairs.
Sample Solution:
C Code:
// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define a structure to represent key-value pairs
struct KeyValuePair {
char key[50];
int value;
struct KeyValuePair* next;
};
// Define a structure to represent the 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;
}
// Function to calculate the hash value of a key
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);
struct KeyValuePair* newPair = createKeyValuePair(key, value);
newPair->next = hashTable->table[index];
hashTable->table[index] = newPair;
}
// Function to retrieve the value associated with a key from the hash table
int retrieve(struct HashTable* hashTable, const char* key) {
unsigned int index = hashFunction(key, hashTable->size);
struct KeyValuePair* current = hashTable->table[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return -1; // Return -1 if the key is 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;
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
if (previous == NULL) {
hashTable->table[index] = current->next;
} else {
previous->next = current->next;
}
free(current);
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() {
// Create a hash table with a size of 10
struct HashTable* hashTable = createHashTable(10);
// Insert key-value pairs into the hash table
insert(hashTable, "Alaric", 35);
insert(hashTable, "Faustus", 28);
insert(hashTable, "Wilbur", 30);
insert(hashTable, "Melcha", 31);
// Display the initial state of the hash table
printf("Initial Hash Table:\n");
displayHashTable(hashTable);
printf("\n");
// Retrieve and print values for specific keys
printf("Value for key 'Alaric': %d\n", retrieve(hashTable, "Alaric"));
printf("Value for key 'Faustus': %d\n", retrieve(hashTable, "Faustus"));
printf("Value for key 'Cambria': %d\n", retrieve(hashTable, "Cambria"));
printf("\n");
// Remove a key-value pair and display the updated hash table
printf("Deleting key 'Faustus'\n");
removeKey(hashTable, "Faustus");
displayHashTable(hashTable);
printf("\n");
// Free the memory allocated for the hash table
freeHashTable(hashTable);
return 0;
}
Output:
Initial Hash Table: [0] -> NULL [1] -> (Faustus, 28) -> NULL [2] -> NULL [3] -> NULL [4] -> NULL [5] -> (Melcha, 31) -> NULL [6] -> NULL [7] -> NULL [8] -> (Wilbur, 30) -> NULL [9] -> (Alaric, 35) -> NULL Value for key 'Alaric': 35 Value for key 'Faustus': 28 Value for key 'Cambria': -1 Deleting key 'Faustus' [0] -> NULL [1] -> NULL [2] -> NULL [3] -> NULL [4] -> NULL [5] -> (Melcha, 31) -> NULL [6] -> NULL [7] -> NULL [8] -> (Wilbur, 30) -> NULL [9] -> (Alaric, 35) -> NULL
Explanation:
In the exercise above,
- Structures:
- KeyValuePair: Represents a key-value pair with a key (string) and a value (integer), and a pointer to the next pair in case of collision.
- HashTable: Represents a hash table with a specified size and an array of pointers to KeyValuePair.
- Functions:
- createKeyValuePair: Allocates memory for a new key-value pair and initializes its values.
- createHashTable: Allocates memory for a new hash table with a specified size and initializes its array of pointers.
- hashFunction: Calculates the hash value of a given key using a simple hashing algorithm.
- insert: Inserts a new key-value pair into the hash table using the calculated hash value.
- retrieve: Retrieves the value associated with a key from the hash table.
- removeKey: Removes a key-value pair from the hash table.
- displayHashTable: Displays the contents of the hash table, including chains in case of collisions.
- freeHashTable: Frees the memory allocated for the hash table, including all key-value pairs.
- Main Function:
- Creates a hash table with a size of 10.
- Inserts several key-value pairs into the hash table.
- Displays the initial state of the hash table.
- Retrieves and prints values for specific keys.
- Removes a key-value pair and displays the updated hash table.
- Frees the memory allocated for the hash table.
Flowchart:
C Programming Code Editor:
Previous: C Program: Hash Table Implementation and Operations Home.
Next: Hash Table in C with collision Handling: Insertion, deletion, retrieval.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics