Hash Tables with Separate Chaining in C

This article explains how to build a hash table in C using separate chaining to handle key collisions. It covers the underlying architectural concepts, the definition of custom linked list and table structures, the creation of a hash function, and the implementation of essential operations including insertion, retrieval, and dynamic memory deallocation.

Understanding Separate Chaining

A hash table maps keys to values using a hash function that computes an index into an array of buckets. When two distinct keys produce the same index, a collision occurs.

Separate chaining resolves collisions by turning each bucket into an independent linked list. When multiple keys hash to the same bucket index, the new key-value pair is simply appended or prepended to the linked list at that index. This approach ensures the table never runs out of space for new entries, bounded only by available system memory.

Defining the Data Structures

In C, separate chaining requires two primary structures: a node structure for the linked list elements and a table structure that manages the bucket array.

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

#define TABLE_SIZE 10

typedef struct Node {
    char *key;
    char *value;
    struct Node *next;
} Node;

typedef struct HashTable {
    Node **buckets;
    int size;
} HashTable;

Node stores string keys, string values, and a pointer to the subsequent node in the chain. HashTable contains an array of Node pointers (buckets) and tracks the table's total bucket capacity.

Implementing the Hash Function

The hash function converts an arbitrary key into a deterministic integer, which is then mapped to a valid bucket index using the modulo operator. The djb2 algorithm is widely used for string hashing due to its speed and distribution quality:

unsigned int hash(const char *key, int size) {
    unsigned long int hash_val = 5381;
    int c;

    while ((c = *key++)) {
        hash_val = ((hash_val << 5) + hash_val) + c; /* hash * 33 + c */
    }

    return (unsigned int)(hash_val % size);
}

Initializing the Table

Creating the hash table requires allocating memory for the table struct and setting all bucket pointers to NULL.

HashTable *create_table(int size) {
    HashTable *table = malloc(sizeof(HashTable));
    if (!table) return NULL;

    table->size = size;
    table->buckets = calloc(table->size, sizeof(Node *));
    if (!table->buckets) {
        free(table);
        return NULL;
    }

    return table;
}

Insertion with Collision Handling

To insert a key-value pair:

  1. Compute the bucket index using hash().
  2. Traverse the list at that bucket to check if the key already exists. If found, update its value.
  3. If the key does not exist, allocate a new node and insert it at the head of the list for \(O(1)\) insertion performance.
void insert(HashTable *table, const char *key, const char *value) {
    unsigned int index = hash(key, table->size);
    Node *current = table->buckets[index];

    // Check for existing key and update value
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            free(current->value);
            current->value = strdup(value);
            return;
        }
        current = current->next;
    }

    // Allocate new node
    Node *new_node = malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = strdup(value);
    
    // Insert at head
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;
}

Searching for Keys

Retrieving a value requires hashing the target key to find the corresponding bucket and traversing the chain until a match is found.

char *search(HashTable *table, const char *key) {
    unsigned int index = hash(key, table->size);
    Node *current = table->buckets[index];

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }

    return NULL; // Key not found
}

Memory Management

Because dynamic allocation is used for the table, the bucket array, the nodes, and the strings, all allocated blocks must be freed systematically to avoid memory leaks.

void free_table(HashTable *table) {
    for (int i = 0; i < table->size; i++) {
        Node *current = table->buckets[i];
        while (current != NULL) {
            Node *temp = current;
            current = current->next;
            free(temp->key);
            free(temp->value);
            free(temp);
        }
    }
    free(table->buckets);
    free(table);
}

Performance Characteristics

With a uniform hash distribution, separate chaining provides average-case time complexities of \(O(1)\) for insertion, search, and deletion. If the hash function produces significant clustering or the load factor (ratio of items to bucket size) becomes excessively high, operations degrade to \(O(n)\), behaving identically to a single linked list. Maintaining an appropriate table size relative to the expected number of entries preserves optimal throughput.