Hash Table with Chaining for Collision Resolution

Welcome back! In our last lesson, we explored the theoretical side of hash tables, understanding what hash functions are and why collisions are an unavoidable part of the process. We conceptually touched upon two ways to resolve these collisions: open addressing and separate chaining.

Today, we transition from theory to practice. We will implement our own hash table from the ground up in C. Specifically, your goal is to implement a basic hash table using chaining to handle collisions. This approach uses an array of linked lists, which is a perfect exercise to combine your knowledge of structs, pointers, dynamic memory, and linked lists into one powerful data structure.

Let's get started.

1. The Structure of a Chained Hash Table

In the separate chaining strategy, our hash table is fundamentally an array. However, each slot in this array doesn't hold a single value. Instead, it holds a pointer to the head of a linked list. All items that hash to the same index will be stored in this list.

To implement this in C, we need two struct definitions:

1. A struct for the nodes of our linked lists. Each node must store the key, the value, and a pointer to the next node in the chain.
2. A struct for the hash table itself. This will contain the array of pointers to our nodes and the size of that array.

Here is a common way to define these structures:

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

// A node in the hash table's linked list
typedef struct person {
    char *name;
    int age;
    struct person *next;
} person_t;

// The hash table structure
typedef struct {
    int size;
    person_t **table; // An array of pointers to person_t nodes
} hashtable_t;

Notice the person_t **table;. This is a pointer to a pointer. It represents a dynamically allocated array (*table) where each element is itself a pointer to a person_t node (person_t *). Initially, all these pointers in the array will be NULL.

2. Implementing the Core Logic

Now, let's walk through the implementation of the essential hash table functions. We will use a video guide that builds a complete hash table from scratch, explaining each step clearly. It uses a slightly different struct name but the concept is identical to what we've just defined.

Let's break down the logic for the key functions discussed in the video.

Creating the Hash Table

The first step is to create a function that allocates memory for our hash table and initializes it.

hashtable_t *ht_create(int size) {
    // Allocate memory for the table structure
    hashtable_t *hashtable = malloc(sizeof(hashtable_t));
    if (hashtable == NULL) {
        return NULL;
    }

    hashtable->size = size;

    // Allocate memory for the array of pointers (the "buckets")
    hashtable->table = calloc(size, sizeof(person_t *));
    if (hashtable->table == NULL) {
        free(hashtable); // Clean up
        return NULL;
    }

    // `calloc` initializes the memory to zero, so all pointers are already NULL.
    
    return hashtable;
}

This function creates the main hashtable_t struct and the internal array of person_t* pointers. Using calloc is convenient here as it zeroes out the memory, ensuring every "bucket" in our table starts as a NULL pointer, indicating an empty list.

Inserting an Element (with Chaining)

The insert function is the heart of our implementation. It must handle three scenarios:

1. The bucket is empty.
2. The bucket is not empty (a collision), and we need to add a new, unique key.
3. The bucket is not empty, and the key we are inserting already exists (in which case we should update the value).

Here is the logic for inserting a new node at the head of the chain, which is the simplest and most common approach:

// A simple hash function
unsigned int hash(const char *key, int size) {
    unsigned long int hash_value = 0;
    int c;
    while ((c = *key++)) {
        hash_value = c + (hash_value << 6) + (hash_value << 16) - hash_value;
    }
    return hash_value % size;
}

// Insert a key-value pair
void ht_insert(hashtable_t *ht, const char *key, int age) {
    // 1. Calculate the hash to find the index
    unsigned int index = hash(key, ht->size);

    // Optional: Traverse the list at ht->table[index] to check for duplicates
    // and update if the key is found. For simplicity, we will skip this
    // and allow duplicate keys, but a robust implementation would handle updates.
    
    // 2. Create the new person node
    person_t *new_person = malloc(sizeof(person_t));
    new_person->name = strdup(key); // Use strdup to copy the key
    new_person->age = age;
    
    // 3. Insert the new node at the head of the list
    new_person->next = ht->table[index];
    ht->table[index] = new_person;
}

This logic is beautifully simple. We treat the array slot ht->table[index] exactly like the head of a normal linked list. The new item is created, its next pointer is set to the current head of the list, and then the head is updated to point to the new item.

Looking Up an Element

To find an element, we first hash the key to find the correct bucket. Then, we perform a standard linear search on the linked list in that bucket.

person_t *ht_lookup(hashtable_t *ht, const char *key) {
    // 1. Calculate the hash to find the index
    unsigned int index = hash(key, ht->size);

    // 2. Start at the head of the list for this index
    person_t *current = ht->table[index];

    // 3. Traverse the list, comparing keys
    while (current != NULL) {
        if (strcmp(current->name, key) == 0) {
            return current; // Found it!
        }
        current = current->next;
    }

    // 4. If the loop finishes, the key was not found
    return NULL;
}

This demonstrates the trade-off of chaining. If the hash function is good and the table is sized well, the lists will be very short, and this lookup will be extremely fast. In the worst case (many collisions at one index), it degrades to the speed of a linked list search, $O(n)$.

3. Putting it all together and testing

For a complete picture, including functions for delete and printing the table, this article provides a full implementation that you can read and study. It uses slightly different function and variable names, but the logic is identical to what we've discussed.

Your task now is to combine these pieces into a working C program. Try to write the code yourself, using the video and article as your guides.

Example main function to test your code:

int main() {
    // Create a table of size 10
    hashtable_t *ht = ht_create(10);

    // Insert some people. Note that "Ron" and "Marin" will likely collide.
    ht_insert(ht, "Jacob", 35);
    ht_insert(ht, "Kate", 28);
    ht_insert(ht, "Mpo", 31);
    ht_insert(ht, "Ron", 40);
    ht_insert(ht, "Marin", 25);
    ht_insert(ht, "Bill", 55);

    // Look up some people
    person_t *found = ht_lookup(ht, "Kate");
    if (found != NULL) {
        printf("Found Kate, age: %d\n", found->age);
    } else {
        printf("Kate not found.\n");
    }

    found = ht_lookup(ht, "George");
    if (found != NULL) {
        printf("Found George, age: %d\n", found->age);
    } else {
        printf("George not found.\n");
    }
    
    // Remember to free all allocated memory at the end!
    // (A ht_free() function would be needed for a complete implementation)

    return 0;
}

Conclusion

Congratulations on building a hash table! This is a significant milestone that combines many of the C programming concepts you've learned into a single, highly efficient data structure.

Key Takeaways:

• A chained hash table is an array where each element is a pointer to the head of a linked list.
• Insertion involves hashing the key to find the array index and then adding the new element to the front of the linked list at that index.
• Lookup involves hashing the key to find the index, then traversing the corresponding linked list to find the element with a matching key.
• The implementation relies heavily on structs to define the data, pointers for the linking, and malloc/free for dynamic memory management.

Preview of the Next Lesson:
Now that we have implemented arrays, Binary Search Trees, and hash tables, how do we decide which one to use? In the next lesson, we will formally compare the average-case time complexity of search operations in these data structures. This will help you understand their performance trade-offs and make informed decisions when solving problems.