C Program: Collision Resolution Performance Analysis

Last update on December 09 2023 16:04:30 (UTC/GMT +8 hours)

C Program to implement Hash Tables: Exercise-8 with Solution

Write a C program that compares the performance of different collision resolution methods (chaining, linear probing, etc.) in terms of speed and memory usage.

Sample Solution:

C Code:

// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <chrono>

#define TABLE_SIZE 10000

// 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 using chaining
void insertChaining(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 using chaining
const char* retrieveChaining(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;
    }
    return "Key not found"; // Key not found
}

// Function to free the memory allocated for the hash table using chaining
void freeHashTableChaining(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);
}

// Function to insert a key-value pair into the hash table using linear probing
void insertLinearProbing(struct HashTable* hashTable, const char* key, const char* value) {
    unsigned long index = hashFunction(key) % hashTable->size;

    // Linear probing to find an empty slot
    while (hashTable->table[index] != NULL) {
        index = (index + 1) % hashTable->size;
    }

    // Create a new key-value pair
    struct KeyValuePair* newPair = createKeyValuePair(key, value);
    hashTable->table[index] = newPair;
}

// Function to retrieve the value associated with a key using linear probing
const char* retrieveLinearProbing(struct HashTable* hashTable, const char* key) {
    unsigned long index = hashFunction(key) % hashTable->size;

    // Linear probing to find the key
    while (hashTable->table[index] != NULL) {
        if (strcmp(hashTable->table[index]->key, key) == 0) {
            return hashTable->table[index]->value; // Key found, return the value
        }
        index = (index + 1) % hashTable->size;
    }
    return "Key not found"; // Key not found
}

// Function to free the memory allocated for the hash table using linear probing
void freeHashTableLinearProbing(struct HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        free(hashTable->table[i]);
    }

    free(hashTable->table);
    free(hashTable);
}

// Function to perform performance testing with chaining
void testChaining() {
    struct HashTable* hashTable = createHashTable(TABLE_SIZE);

    // Insert key-value pairs
    for (int i = 0; i < TABLE_SIZE; i++) {
        char key[50];
        char value[50];
        sprintf(key, "Key%d", i);
        sprintf(value, "Value%d", i);
        insertChaining(hashTable, key, value);
    }

    // Retrieve key-value pairs
    for (int i = 0; i < TABLE_SIZE; i++) {
        char key[50];
        sprintf(key, "Key%d", i);
        const char* result = retrieveChaining(hashTable, key);
        printf("Chaining - Retrieved value for key '%s': %s\n", key, result);
    }

    // Free allocated memory
    freeHashTableChaining(hashTable);
}

// Function to perform performance testing with linear probing
void testLinearProbing() {
    struct HashTable* hashTable = createHashTable(TABLE_SIZE);

    // Insert key-value pairs
    for (int i = 0; i < TABLE_SIZE; i++) {
        char key[50];
        char value[50];
        sprintf(key, "Key%d", i);
        sprintf(value, "Value%d", i);
        insertLinearProbing(hashTable, key, value);
    }

    // Retrieve key-value pairs
    for (int i = 0; i < TABLE_SIZE; i++) {
        char key[50];
        sprintf(key, "Key%d", i);
        const char* result = retrieveLinearProbing(hashTable, key);
        printf("Linear Probing - Retrieved value for key '%s': %s\n", key, result);
    }

    // Free allocated memory
    freeHashTableLinearProbing(hashTable);
}

int main() {
    // Perform performance testing with chaining
    auto startChaining = std::chrono::high_resolution_clock::now();
    testChaining();
    auto endChaining = std::chrono::high_resolution_clock::now();
    auto durationChaining = std::chrono::duration_cast<std::chrono::microseconds>(endChaining - startChaining);

    // Perform performance testing with linear probing
    auto startLinearProbing = std::chrono::high_resolution_clock::now();
    testLinearProbing();
    auto endLinearProbing = std::chrono::high_resolution_clock::now();
    auto durationLinearProbing = std::chrono::duration_cast<std::chrono::microseconds>(endLinearProbing - startLinearProbing);

    // Print performance results
    printf("\nPerformance Results:\n");
    printf("Chaining Duration: %lld microseconds\n", durationChaining.count());
    printf("Linear Probing Duration: %lld microseconds\n", durationLinearProbing.count());

    return 0;
}

Output:

Linear Probing - Retrieved value for key 'Key1007': Value1007
Linear Probing - Retrieved value for key 'Key1008': Value1008
Linear Probing - Retrieved value for key 'Key1009': Value1009
Linear Probing - Retrieved value for key 'Key1010': Value1010
Linear Probing - Retrieved value for key 'Key1011': Value1011
Linear Probing - Retrieved value for key 'Key1012': Value1012
Linear Probing - Retrieved value for key 'Key1013': Value1013
Linear Probing - Retrieved value for key 'Key1014': Value1014
Linear Probing - Retrieved value for key 'Key1015': Value1015
Linear Probing - Retrieved value for key 'Key1016': Value1016
Linear Probing - Retrieved value for key 'Key1017': Value1017
Linear Probing - Retrieved value for key 'Key1018': Value1018
Linear Probing - Retrieved value for key 'Key1019': Value1019
-  -  -  -  -  -  -  - -  -  -  -  -  -  -  -  -  - -  -  -  -  -  -  -  -  -  -
-  -  -  -  -  -  -  - -  -  -  -  -  -  -  -  -  - -  -  -  -  -  -  -  -  -  -

Explanation:

In the exercise above,

Hash table structure:

The program defines a structure 'KeyValuePair' for a key-value pair and a structure 'HashTable' for a hash table.
The hash table uses an array of pointers to 'KeyValuePair' structures (struct KeyValuePair** table).

Hash function:

The hashFunction is a simple hash function (djb2 algorithm) that generates a hash value for a given string.

Key-Value Pair Creation:

The createKeyValuePair function dynamically allocates memory for a new key-value pair and initializes its fields.

Hash table creation:

The createHashTable function dynamically allocates memory for a new hash table and initializes its fields.

Chaining Operations:

insertChaining: Inserts a key-value pair into the hash table using chaining.
retrieveChaining: Retrieves the value associated with a key using chaining.
freeHashTableChaining: Frees the memory allocated for the hash table using chaining.

Linear probing operations:

insertLinearProbing: Inserts a key-value pair into the hash table using linear probing.
retrieveLinearProbing: Retrieves the value associated with a key using linear probing.
freeHashTableLinearProbing: Frees the memory allocated for the hash table using linear probing.

Performance testing:

The testChaining and testLinearProbing functions perform performance testing for chaining and linear probing, respectively.
Key-value pairs are inserted into the hash table, and then retrieval operations are performed.

Main functions:

The "main()" function measures the duration of the chaining and linear probing tests using the library for timing.
The program prints the duration of each test, providing insights into the performance of the two collision resolution methods.

Flowchart:

C Programming Code Editor:

Previous: C Program: Hash Table with Open Addressing.
Next: Creating a Generic Hash table in C for flexible data storage.