Implementing Hash Tables with Separate Chaining

What is a Hash Table?

At its core, a hash table is a data structure designed for extremely fast key-value lookups, insertions, and deletions. While a linked list search is O(n), the ideal hash table operation is O(1)—constant time, regardless of how many items are in the table.

Let's start with a quick conceptual overview.

As the video explains, a hash table combines two key components:

1. An array (which we'll call the buckets).
2. A hash function that maps a given key to an index in that array.

However, this simple model has a problem: what happens when the hash function maps two different keys to the same index? This is called a collision. Our design must handle this gracefully.

Collision Resolution: Separate Chaining

The most common strategy for handling collisions is separate chaining. Instead of storing one item per bucket, each bucket acts as a pointer to the head of a linked list. When a collision occurs, the new key-value pair is simply added to the linked list at that bucket's index.

This image from the Algorithms, 4th Edition textbook website perfectly illustrates the concept.

To see how this looks in practice, let's watch another clip that walks through implementing this.

Designing the C Data Structures

Now we get to the core of today's lesson: translating this concept into a robust and generic C design. Since your goal is to build practical, reusable code, we won't hardcode the key and value types (e.g., as char*). Instead, we'll use void* pointers and function pointers to create a generic hash table that can store any data type.

A comprehensive guide from andreinc.net provides an excellent model for this. We will adopt its design.

Let's break down this design.

1. The Node Structure (ch_node)

This is the building block for our linked lists. Each node stores a single key-value pair.

typedef struct ch_node_s {
    uint32_t hash;      // The pre-calculated hash of the key
    void *key;          // Generic pointer to the key
    void *val;          // Generic pointer to the value
    struct ch_node_s *next; // Pointer to the next node in the chain
} ch_node;

• Storing the hash value directly in the node is a common optimization. It avoids re-calculating the hash when searching within a linked list or when resizing the table.
• Using void *key and void *val makes our hash table generic. The table itself doesn't need to know if it's storing strings, integers, or complex structs.

2. The Hash Table Structure (ch_hash)

This is the main structure that holds everything together.

typedef struct ch_hash_s {
    size_t capacity;     // The number of buckets in our array
    size_t size;         // The number of key-value pairs currently stored
    ch_node **buckets;   // The array of buckets (array of pointers to nodes)
    ch_key_ops key_ops;  // Function pointers for handling keys
    ch_val_ops val_ops;  // Function pointers for handling values
} ch_hash;

• buckets is a ch_node **. This is a pointer to a pointer, which is how you create a dynamic array of pointers in C. buckets[i] will be a ch_node *, pointing to the first node in the chain for that bucket.
• key_ops and val_ops are the key to making this design generic.

3. The Operations Structures (ch_key_ops, ch_val_ops)

Since the hash table uses void*, it doesn't know how to hash a key, compare two keys, or free the memory for a key. We must provide this logic to the hash table when we create it. This is done via function pointers.

// Operations for the KEY
typedef struct ch_key_ops_s {
    uint32_t (*hash)(const void *data, void *arg); // Hash the key
    void* (*cp)(const void *data, void *arg);     // Copy the key
    void (*free)(void *data, void *arg);          // Free the key
    bool (*eq)(const void *data1, const void *data2, void *arg); // Compare two keys
    void *arg; // Optional user-defined argument for the functions
} ch_key_ops;

// Operations for the VALUE (similar, but no hash function)
typedef struct ch_val_ops_s {
    void* (*cp)(const void *data, void *arg);
    void (*free)(void *data, void *arg);
    bool (*eq)(const void *data1, const void *data2, void *arg);
    void *arg;
} ch_val_ops;

This design pattern is extremely powerful. It separates the generic logic of the hash table data structure from the specific logic required for the data types it contains. When we initialize our hash table, we'll pass it a struct populated with pointers to functions that know how to work with, for example, strings.

Component 4: The Hash Function

The quality of the hash function is paramount for performance. A bad function creates many collisions, turning our hash table into a set of slow linked lists. A good function distributes keys evenly across the buckets.

For string keys, simple functions like summing ASCII values are poor. Well-regarded algorithms like djb2 are far superior.

Here is the C implementation of djb2 from that resource. This is a function that you would point to from your ch_key_ops struct.

// An example of a hash function for strings (djb2)
uint32_t string_hash_djb2(const void *data, void *arg) {
    // We cast the generic void* back to what we know it is.
    const char *str = (const char*) data;
    uint32_t hash = 5381;
    char c;

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

    return hash;
}

The final step is to map this large hash value to a bucket index, which is typically done with the modulo operator: size_t index = hash % table->capacity;.

Conclusion

In this lesson, we have laid the complete architectural groundwork for a generic, non-thread-safe hash table in C.

Key Takeaways:

• A hash table uses a hash function to map keys to an array of buckets.
• Separate chaining is a collision resolution strategy where each bucket is the head of a linked list.
• A robust C design can be made generic using void* pointers for data and function pointers (struct *_ops) for data-specific operations like hashing, copying, and comparison.
• The choice of hash function (e.g., djb2 for strings) is critical for performance, as it determines how evenly keys are distributed and thus how short the linked-list chains are.

Preview of the Next Lesson:
We have the blueprint. In the next lesson, we will bring this design to life by implementing the non-thread-safe operations for the hash table (insert, lookup, delete). With a working implementation in hand, we will then be ready to tackle the main challenge of this module: making it all thread-safe.