C Program: Hash Table with Open Addressing

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

Write a C program that implements a hash table using open addressing techniques like linear probing or quadratic probing to resolve collisions.

Sample Solution:

C Code:

// Including necessary header files
#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];
};

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

// Function to create a new key-value pair
struct KeyValuePair createKeyValuePair(const char* key, const char* value) {
    struct KeyValuePair newPair;
    strcpy(newPair.key, key);
    strcpy(newPair.value, value);
    return newPair;
}

// Function to create a new hash table
struct HashTable createHashTable(int size) {
    struct HashTable newTable;
    newTable.size = size;
    newTable.itemCount = 0;
    newTable.table = (struct KeyValuePair*)calloc(size, sizeof(struct KeyValuePair));
    return newTable;
}

// 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 resolve collisions using linear probing
int linearProbe(int index, int attempt, int size) {
    return (index + attempt) % size;
}

// Function to insert a key-value pair into the hash table using linear probing
void insert(struct HashTable* hashTable, const char* key, const char* value) {
    if (hashTable->itemCount >= hashTable->size) {
        printf("Hash table is full. Cannot insert more items.\n");
        return;
    }

    unsigned long index = hashFunction(key) % hashTable->size;
    int attempt = 0;

    // Probe until an empty slot is found
    while (hashTable->table[index].key[0] != '\0') {
        attempt++;
        index = linearProbe(index, attempt, hashTable->size);
    }

    // Insert the new pair
    hashTable->table[index] = createKeyValuePair(key, value);
    hashTable->itemCount++;
}

// 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;
    int attempt = 0;

    // Probe until the key is found or an empty slot is encountered
    while (strcmp(hashTable->table[index].key, key) != 0 && hashTable->table[index].key[0] != '\0') {
        attempt++;
        index = linearProbe(index, attempt, hashTable->size);
    }

    if (strcmp(hashTable->table[index].key, key) == 0) {
        return hashTable->table[index].value; // Key found, return the value
    } else {
        return "Key not found"; // Key not found
    }
}

// Function to display the contents of the hash table
void displayHashTable(struct HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        printf("[%d] -> (%s, %s)\n", i, hashTable->table[i].key, hashTable->table[i].value);
    }
}

int main() {
    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 hash table
    printf("Hash Table:\n");
    displayHashTable(&hashTable);

    // Retrieve and print values for specific keys
    printf("\nValue 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"));

    return 0;
}

Output:

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

Value for key 'Red': #ff0000
Value for key 'Yellow': #FFFF00
Value for key 'White': Key not found

Explanation:

In the exercise above,

• Structures:
• KeyValuePair: Represents a key-value pair with fields for the key and value.
• HashTable: Represents the hash table with fields for size, item count, and an array of key-value pairs.
• Hash Function (hashFunction):
• Utilizes the djb2 algorithm to hash strings and generate an index.
• Probing Function (linearProbe):
• Resolves collisions using linear probing, which means it probes linearly through the array until an empty slot is found.
• createKeyValuePair Function:
• Creates a new key-value pair.
• createHashTable Function:
• Creates a new hash table with a specified size.
• insert Function:
• Inserts a key-value pair into the hash table.
• Uses the hash function to find an initial index and linear probing to handle collisions.
• retrieve Function:
• Retrieves the value associated with a key from the hash table.
• Utilizes the hash function and linear probing to find the correct index.
• displayHashTable Function:
• Displays the contents of the hash table.
• main Function:
• Create a hash table.
• Inserts several key-value pairs into the hash table.
• Displays the contents of the hash table.
• Retrieves and prints values for specific keys.

Flowchart:

C Programming Code Editor:

Previous: C Program: Calculate Hash table statistics.
Next: C Program: Collision Resolution Performance Analysis.