How To Implement A Hash Table In C?

A hash table is a powerful data structure that allows efficient insertion, deletion, and retrieval of key-value pairs.

It uses a hash function to map keys to indices in an array, providing constant-time average complexity for these operations.

In this comprehensive guide, we will explore the fundamental concepts of hash tables and implement a simple version in C.

Table of Contents #

  1. Understanding Hash Tables
  2. Designing a Basic Hash Table Structure
  3. Hash Function
  4. Insertion into the Hash Table
  5. Searching in the Hash Table
  6. Deletion from the Hash Table
  7. Testing the Hash Table
  8. Conclusion

Understanding Hash Tables

A hash table consists of an array of buckets, each associated with a unique index. The keys are hashed using a hash function, and the resulting hash code determines the index where the corresponding value will be stored.

Collision handling is a crucial aspect of hash tables, as multiple keys may hash to the same index.

Common collision resolution techniques include chaining (linked lists in each bucket) or open addressing.

Designing a Basic Hash Table Structure

Let's start by designing a basic hash table structure in C. For simplicity, we'll use chaining to handle collisions.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define a structure for key-value pairs
struct KeyValuePair {
    char* key;
    int value;
    struct KeyValuePair* next; // Pointer to the next key-value pair in case of collisions
};

// Define the HashTable structure
struct HashTable {
    int size;
    struct KeyValuePair** table; // Array of pointers to key-value pairs (buckets)
};

// Function to create a new key-value pair
struct KeyValuePair* createKeyValuePair(const char* key, int value) {
    struct KeyValuePair* pair = (struct KeyValuePair*)malloc(sizeof(struct KeyValuePair));
    pair->key = strdup(key);
    pair->value = value;
    pair->next = NULL;
    return pair;
}

// Function to create a new hash table
struct HashTable* createHashTable(int size) {
    struct HashTable* hashTable = (struct HashTable*)malloc(sizeof(struct HashTable));
    hashTable->size = size;
    hashTable->table = (struct KeyValuePair**)calloc(size, sizeof(struct KeyValuePair*));
    return hashTable;
}

In this design, KeyValuePair represents a key-value pair, and HashTable represents the hash table itself.

The createKeyValuePair function creates a new key-value pair, and createHashTable initializes a new hash table with a specified size.

Hash Function

A hash function takes a key and returns an index within the range of the hash table size. A simple hash function for strings could sum the ASCII values of characters, but for demonstration purposes, we'll use a basic one that calculates the modulo of the string length.

// Function to calculate the hash code for a key
int hashCode(const char* key, int tableSize) {
    int hash = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hash += key[i];
    }
    return hash % tableSize;
}

Insertion into the Hash Table

The insert function adds a key-value pair to the hash table. If a collision occurs, it adds the new pair to the linked list in the corresponding bucket.

// Function to insert a key-value pair into the hash table
void insert(struct HashTable* hashTable, const char* key, int value) {
    int index = hashCode(key, hashTable->size);
    struct KeyValuePair* pair = createKeyValuePair(key, value);

    // If the bucket is empty, insert the new pair
    if (hashTable->table[index] == NULL) {
        hashTable->table[index] = pair;
    } else {
        // Handle collision by chaining
        struct KeyValuePair* current = hashTable->table[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = pair;
    }
}

Searching in the Hash Table

The search function finds the value associated with a given key in the hash table. If the key is not found, it returns a special value (e.g., -1).

// Function to search for a key in the hash table and return its value
int search(struct HashTable* hashTable, const char* key) {
    int index = hashCode(key, hashTable->size);
    struct KeyValuePair* current = hashTable->table[index];

    // Traverse the linked list in the bucket
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value; // Key found
        }
        current = current->next;
    }

    return -1; // Key not found
}

Deletion from the Hash Table

The delete function removes a key-value pair from the hash table based on the given key.

// Function to delete a key-value pair from the hash table
void delete(struct HashTable* hashTable, const char* key) {
    int index = hashCode(key, hashTable->size);
    struct KeyValuePair* current = hashTable->table[index];
    struct KeyValuePair* prev = NULL;

    // Traverse the linked list in the bucket
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            // Key found, remove the pair
            if (prev == NULL) {
                // If it's the first in the list
                hashTable->table[index] = current->next;
            } else {
                prev->next = current->next;
            }

            free(current->key);
            free(current);
            return;
        }

        prev = current;
        current = current->next;
    }
}

Testing the Hash Table

Now, let's test our hash table implementation with a simple example:

int main() {
    struct HashTable* hashTable = createHashTable(10);

    // Insert key-value pairs
    insert(hashTable, "apple", 5);
    insert(hashTable, "banana", 8);
    insert(hashTable, "orange", 12);

    // Search for values
    printf("Value for 'apple': %d\n", search(hashTable, "apple"));
    printf("Value for 'banana': %d\n", search(hashTable, "banana"));
    printf("Value for 'orange': %d\n", search(hashTable, "orange"));
    printf("Value for 'grape': %d\n", search(hashTable, "grape"));

    // Delete a key-value pair


    delete(hashTable, "banana");

    // Attempt to search for the deleted key
    printf("Value for 'banana' after deletion: %d\n", search(hashTable, "banana"));

    return 0;
}

In this example, we create a hash table, insert key-value pairs, search for values, delete a key-value pair, and attempt to search for the deleted key.

Conclusion

Implementing a hash table in C involves designing a structure for key-value pairs, creating a hash function, and handling collisions.

The choice of collision resolution strategy (chaining, open addressing) depends on the specific requirements of your application.

Understanding the principles behind hash tables is crucial for developing efficient and scalable solutions in various programming scenarios.