﻿ C Program: Calculate Hash table statistics

# C Program: Calculate Hash table statistics

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

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;

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:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿