C Program: Calculate Hash table statistics

Last update on December 20 2024 13:05:21 (UTC/GMT +8 hours)

Write a C program that calculates and displays statistics about the hash table, such as load factor, average chain length, and distribution.

Sample Solution:

C Code:

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

#define TABLE_SIZE 10

// Forward declarations
struct HashTable* createHashTable(int size);
void insert(struct HashTable* hashTable, const char* key, const char* value);
void displayStatistics(struct HashTable* hashTable);

// 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;
    int itemCount;
    int maxChainLength;
    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->itemCount = 0;
        newTable->maxChainLength = 0;
        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;

    // Update the item count
    hashTable->itemCount++;

    // Update the maximum chain length
    int chainLength = 0;
    struct KeyValuePair* current = hashTable->table[index];
    while (current != NULL) {
        chainLength++;
        current = current->next;
    }
    if (chainLength > hashTable->maxChainLength) {
        hashTable->maxChainLength = chainLength;
    }
}

// Function to display statistics about the hash table
void displayStatistics(struct HashTable* hashTable) {
    double loadFactor = (double)hashTable->itemCount / hashTable->size;
    printf("Load Factor: %.2f\n", loadFactor);

    int totalChainLength = 0;
    int nonEmptyBuckets = 0;

    for (int i = 0; i < hashTable->size; i++) {
        struct KeyValuePair* current = hashTable->table[i];
        int chainLength = 0;

        while (current != NULL) {
            chainLength++;
            current = current->next;
        }

        if (chainLength > 0) {
            totalChainLength += chainLength;
            nonEmptyBuckets++;
        }
    }

    double averageChainLength = (double)totalChainLength / nonEmptyBuckets;
    printf("Average Chain Length: %.2f\n", averageChainLength);
    printf("Maximum Chain Length: %d\n", hashTable->maxChainLength);
}

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 statistics
    displayStatistics(hashTable);

    // Free allocated memory
    free(hashTable);

    return 0;
}

Output:

Load Factor: 0.50
Average Chain Length: 1.25
Maximum Chain Length: 2

Explanation:

In the exercise above -

Structures:

KeyValuePair: Represents a key-value pair with fields for a key, value, and a pointer to the next pair in case of a collision.
HashTable: Represents the hash table with fields for size, item count, maximum chain length, and an array of pointers to 'KeyValuePair' representing buckets.

Hash Function (hashFunction):

Implements the djb2 algorithm to generate a hash value for a given string.

Functions:

createKeyValuePair: Allocates memory for a new key-value pair and initializes its fields.
createHashTable: Allocates memory for creating a hash table, including an array of buckets, and initializes its fields.
insert: Inserts a new key-value pair into the hash table, handling collisions using chaining. Updates item count and maximum chain length.
displayStatistics: Calculates and displays statistics about the hash table, including load factor, average chain length, and maximum chain length.

Main Function (main):

Creates a hash table, inserts some key-value pairs, and displays statistics using the "displayStatistics()" function.
Adjust the 'TABLE_SIZE' macro for the desired hash table size.

Flowchart:

C Programming Code Editor:

Previous: Hash Table Operations in C: Insert, Delete, and Search.
Next: C Program: Hash Table with Open Addressing.