﻿ C Program: Hash Table Operations - Insert, Delete, Search

# Hash Table Operations in C: Insert, Delete, and Search

## C Program to implement Hash Tables: Exercise-5 with Solution

Write a C program that performs various operations on a hash table, including inserting, deleting, and searching for elements.

Sample Solution:

C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// Structure for a key-value pair
struct KeyValuePair {
char key[50];
char value[50];
struct KeyValuePair* next;
};

// Structure for the hash table
struct HashTable {
int size;
struct KeyValuePair** table;
};

// Hash function for strings (djb2 algorithm)
unsigned long hashFunction(const char* str) {
unsigned long hash = 5381;
int c;

while ((c = *str++) != '\0') {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}

return hash;
}

// Function to create a new key-value pair
struct KeyValuePair* createKeyValuePair(const char* key, const char* value) {
struct KeyValuePair* newPair = (struct KeyValuePair*)malloc(sizeof(struct KeyValuePair));
if (newPair != NULL) {
strcpy(newPair->key, key);
strcpy(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 insert a key-value pair into the hash table
void insert(struct HashTable* hashTable, const char* key, const char* value) {
unsigned long 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
const char* retrieve(struct HashTable* hashTable, const char* key) {
unsigned long 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;
}
}

// Function to delete a key-value pair from the hash table
void deleteKey(struct HashTable* hashTable, const char* key) {
unsigned long index = hashFunction(key) % hashTable->size;
struct KeyValuePair* current = hashTable->table[index];
struct KeyValuePair* prev = NULL;

// Traverse the linked list at the index
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
// Key found, delete the key-value pair
if (prev == NULL) {
// If the key is in the first node of the linked list
hashTable->table[index] = current->next;
} else {
// If the key is in the middle or end of the linked list
prev->next = current->next;
}

// Free the memory allocated for the key-value pair
free(current);
return;
}

// Move to the next node in the linked list
prev = 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, %s) -> ", 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);
}

int main() {
// Example usage
struct HashTable* hashTable = createHashTable(TABLE_SIZE);

// Insert key-value pairs
insert(hashTable, "Red", "#ff0000");
insert(hashTable, "Green", "#008000");
insert(hashTable, "Blue", "#0000FF");
insert(hashTable, "Yellow", "#FFFF00");
insert(hashTable, "Orange", "#FFA500");

// Display the initial hash table
printf("Initial Hash Table:\n");
displayHashTable(hashTable);
printf("\n");

// Retrieve and print values for specific keys
printf("Value for key 'Red': %s\n", retrieve(hashTable, "Red"));
printf("Value for key 'Yellow': %s\n", retrieve(hashTable, "Yellow"));
printf("Value for key 'White': %s\n", retrieve(hashTable, "White"));
printf("\n");

// Delete a key-value pair
deleteKey(hashTable, "Green");

// Display the hash table after deletion
printf("Hash Table after Deleting 'Green':\n");
displayHashTable(hashTable);
printf("\n");

// Free allocated memory
freeHashTable(hashTable);

return 0;
}

Output:

[1] -> (Orange, #FFA500) -> (Blue, #0000FF) -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> NULL
[6] -> NULL
[7] -> NULL
[8] -> (Red, #ff0000) -> NULL
[9] -> (Yellow, #FFFF00) -> NULL

Value for key 'Red': #ff0000
Value for key 'Yellow': #FFFF00

Hash Table after Deleting 'Green':
[0] -> NULL
[1] -> (Orange, #FFA500) -> (Blue, #0000FF) -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> NULL
[6] -> NULL
[7] -> NULL
[8] -> (Red, #ff0000) -> NULL
[9] -> (Yellow, #FFFF00) -> NULL

Explanation:

In the exercise above,

• Structures:
• KeyValuePair: Represents a key-value pair and is used to create nodes in the linked list.
• HashTable: Represents the hash table, containing a size, an array of linked lists (KeyValuePair** table), and an item count.
• Hash Function (hashFunction):
• Implements the djb2 algorithm to calculate the hash value of a string.
• Functions:
• createKeyValuePair: Allocates memory for a new key-value pair and initializes its values.
• createHashTable: Allocates memory for a new hash table and initializes its size, item count, and table.
• insert: Inserts a new key-value pair into the hash table, handling collisions using separate chaining. Resizes the table if needed based on the load factor threshold.
• retrieve: Retrieves the value associated with a given key from the hash table.
• deleteKey: Deletes a key-value pair from the hash table based on the provided key.
• displayHashTable: Displays the contents of the hash table, showing the linked list structure at each index.
• freeHashTable: Frees the memory allocated for the hash table and its key-value pairs.
• Main Function (main):
• Creates a hash table of a specified size.
• Insert some key-value pairs into the hash table.
• Displays the initial state of the hash table.
• Retrieves and prints values for specific keys.
• Deletes a key-value pair.
• Displays the hash table after deletion.
• Frees allocated memory.

Flowchart:

C Programming Code Editor:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿