C Program: Hash Table with Open Addressing

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

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.