Implementing Hash Sets with Hash Tables: Separate Chaining vs. Open Addressing

A set is a fundamental abstract data type that stores unique elements and powers operations such as membership testing, union, intersection, and set difference. When built on top of a hash table, it is commonly called a Hash Set (HashSet).

While high-level languages provide sets out of the box (e.g., Python’s set, Java’s HashSet, or C++‘s std::unordered_set), implementing an efficient, generic hash set in a systems language like C or C++ requires addressing low-level mechanical realities: key type abstraction, collision resolution strategies, expensive hash recomputations, and safe memory reclamation.

---

1. The Core Abstraction and Two-Step Hashing

A hash set guarantees that duplicate elements are rejected. If an element already exists, an insertion operation is a no-op (or returns false).

Insert("apple") -> OK
Insert("banana") -> OK
Insert("apple")  -> Discarded (already present)

Hash tables index internal buckets using integer indices, but application keys are domain-specific objects—strings, UUIDs, structs, or pointers. Converting an arbitrary key to a bucket index requires a two-step hashing process:

+-----------------------+
| Application Key (k)   |   e.g., "cat", "dog"
+-----------------------+
           |
           v  Step 1: Hash Function (Murmur3, xxHash, FNV-1a)
+-----------------------+
| 32-bit Integer Hash   |   Range: [0, 2^32 - 1]
+-----------------------+
           |
           v  Step 2: Index Compression (hash % capacity OR hash & (capacity - 1))
+-----------------------+
| Bucket / Slot Index   |   Range: [0, capacity - 1]
+-----------------------+

The Inevitability of Collisions

Because the domain of keys is infinite while the table’s capacity $M$ is finite, collisions are inevitable at two distinct levels:

1. Hash Collisions: Two distinct keys produce the identical 32-bit hash: $H(k_1) = H(k_2)$.
2. Slot Collisions: Two distinct keys produce different 32-bit hashes that map to the same bucket index: $H(k_1) \pmod M = H(k_2) \pmod M$.

Reaching a slot index does not guarantee that the element occupying it is the element you are looking for. You cannot rely strictly on matching bucket indices or 32-bit hash codes; an explicit key equality check is always mandatory.

---

2. Low-Level System Design Requirements

To implement a production-grade, generic hash set in C, we must support arbitrary types without sacrificing performance.

Requirement A: Generic Pointer Representation (void*)

To support arbitrary types without templating or code bloat, keys are stored as generic pointers (void*). The hash set stores a reference to the data, agnostic of its internal structure.

Requirement B: Caching the 32-bit Hash Code

Computing hash functions (such as MurmurHash3 or SipHash) across arbitrary-length byte sequences or strings is CPU-intensive. Recomputing the hash every time a bucket is traversed, during a collision probe, or during table resizing degrades performance.

By storing the computed uint32_t hash_key alongside the application pointer, we unlock a massive optimization: short-circuit comparison.

if (stored_node->hash_key == query_hash) {
    if (key_comparator(stored_node->key, query_key)) {
        return FOUND;
    }
}

If the 32-bit hash codes differ, the keys cannot be equal. We avoid invoking the expensive, user-provided equality comparator entirely.

Requirement C: User-Supplied Function Pointers

Because the hash set has no intrinsic knowledge of the data behind a void*, the caller must supply two lifecycle functions during initialization:

1. Key Comparator (key_cmp):

   typedef bool (*key_comparator_fn)(const void *k1, const void *k2);

   Returns true if two keys are semantically equal.

2. Key Destructor (key_destructor):

   typedef void (*key_destructor_fn)(void *key);

   Invoked when an element is removed or replaced, allowing the caller to free allocated memory (e.g., dynamic strings, nested structs).

---

3. Implementation 1: Hash Set with Separate Chaining

In separate chaining, every slot in the primary array is a pointer to the head of a linked list (or an empty bucket). Colliding keys are chained together.

Buckets Array
+---+      +-----------------------------------------+
| 0 | ---> | Hash: 0x8A3F | Key: "cat" | Next: NULL  |
+---+      +-----------------------------------------+
| 1 | ---> NULL
+---+      +-----------------------------------------+     +-----------------------------------------+
| 2 | ---> | Hash: 0x1B4C | Key: "dog" | Next: ------> | Hash: 0x4F9E | Key: "bird"| Next: NULL  |
+---+      +-----------------------------------------+     +-----------------------------------------+

Data Structures

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct Node {
    uint32_t hash_key;
    void *key;
    struct Node *next;
} Node;

typedef struct {
    Node **buckets;
    size_t capacity;          // Total number of bucket slots
    size_t size;              // Total number of stored elements
    key_comparator_fn key_cmp;
    key_destructor_fn key_destructor;
} ChainedHashSet;

The Check-Then-Insert Invariant

In a standard hash map or multiset, insertions can execute in $O(1)$ by prepending elements to the head of the list. In a hash set, uniqueness is mandatory. Before inserting, the chain must be traversed to verify that the key does not already exist.

bool chained_set_insert(ChainedHashSet *set, void *key, uint32_t hash) {
    size_t index = hash % set->capacity;
    Node *curr = set->buckets[index];

    while (curr != NULL) {
        // Short-circuit hash comparison before executing expensive comparator
        if (curr->hash_key == hash && set->key_cmp(curr->key, key)) {
            return false; // Key already exists; discard
        }
        curr = curr->next;
    }

    // Key does not exist: allocate node and prepend to head
    Node *new_node = malloc(sizeof(Node));
    new_node->hash_key = hash;
    new_node->key = key;
    new_node->next = set->buckets[index];
    set->buckets[index] = new_node;
    set->size++;

    return true;
}

Deletion

When deleting from a chained hash set:

1. Search the list using the cached hash_key and key_cmp.
2. Splice the matching node out of the linked list.
3. If a key_destructor was supplied, call set->key_destructor(node->key).
4. Free the node metadata struct.

---

4. Implementation 2: Hash Set with Open Addressing

Open addressing stores all elements directly within the primary array without auxiliary pointer nodes. When collisions occur, subsequent slots are evaluated according to a probing strategy (linear probing, quadratic probing, or double hashing).

Index:    0                 1                 2                 3
+-----------------+-----------------+-----------------+-----------------+
| Empty           | Active          | Soft-Deleted    | Active          |
|                 | Hash: 0x8A3F    | (Tombstone)     | Hash: 0x1B4C    |
|                 | Key: "cat"      |                 | Key: "dog"      |
+-----------------+-----------------+-----------------+-----------------+

Data Structures and Slot States

Because a deleted entry cannot simply be emptied without breaking subsequent probe chains, slots require explicit state flags:

typedef struct {
    bool is_empty;
    bool is_deleted;    // Tombstone marker
    uint32_t hash_key;
    void *key;
} Slot;

typedef struct {
    Slot *slots;
    size_t capacity;
    size_t active_keys; // Number of currently accessible keys
    size_t used_slots;  // active_keys + tombstone slots
    key_comparator_fn key_cmp;
    key_destructor_fn key_destructor;
} OpenAddressingHashSet;

Load Factor Tracking

In open addressing, probe lengths depend on the density of occupied slots. Critically: $\text{Load Factor (}\alpha\text{)} = \frac{\text{used\_slots}}{\text{capacity}} = \frac{\text{active\_keys} + \text{tombstones}}{\text{capacity}}$

If the load factor calculation were based solely on active_keys, accumulating tombstones could severely degrade probe efficiency while delaying resizing.

Lookup and Insertion Under Probing

During traversal:

• Matching: If !slot.is_empty && !slot.is_deleted, first check slot.hash_key == hash. Only run key_cmp if the hashes match.
• Insertion: If a key exists, discard the insertion. If an empty or tombstone slot is reached, reuse the slot, update metadata, and mark the slot as active.

Tombstone Lifecycle and Safe Memory Reclamation

A major source of memory bugs in open addressing implementations is premature memory deallocation during deletion.

Initial State:  [ Slot A: "cat" ] -> [ Slot B: "dog" (probed from A) ]
Operation:      Delete("cat")

If “cat” is removed, slot A becomes a tombstone (is_deleted = true).

The Invariant:

1. Soft Delete (delete operation): Mark the slot is_deleted = true. Decrement active_keys. If the hash set owns the data, you may free the key memory immediately only if the slot’s key pointer is set to NULL to avoid dangling references, and the probing logic never accesses the payload of a tombstone.
2. Hard Delete (resize / rehash operation): When used_slots / capacity crosses a threshold (typically $0.70$), allocate a new array and rehash all active keys into the new table. Tombstone slots are discarded without copying. Any leftover dynamically allocated resources that were not freed during the soft delete must be cleaned up during this migration phase.

void open_set_resize(OpenAddressingHashSet *set, size_t new_capacity) {
    Slot *old_slots = set->slots;
    size_t old_capacity = set->capacity;

    set->slots = calloc(new_capacity, sizeof(Slot));
    for (size_t i = 0; i < new_capacity; i++) {
        set->slots[i].is_empty = true;
    }
    set->capacity = new_capacity;
    set->used_slots = 0;
    set->active_keys = 0;

    for (size_t i = 0; i < old_capacity; i++) {
        if (!old_slots[i].is_empty && !old_slots[i].is_deleted) {
            // Reinsert active element into newly sized table
            open_set_insert_internal(set, old_slots[i].key, old_slots[i].hash_key);
        } else if (old_slots[i].is_deleted && set->key_destructor) {
            // Invoke destructor if memory cleanup was deferred
            // set->key_destructor(old_slots[i].key);
        }
    }

    free(old_slots);
}

---

5. Architectural Comparison: Chaining vs. Open Addressing

Dimension	Chaining-Based Hash Set	Open Addressing Hash Set
Storage Overhead	Node pointers (next), dynamic allocations per element	Flat array; requires state flags (is_empty, is_deleted)
Cache Locality	Poor (linked lists traverse disjoint heap memory)	Exceptional (sequential memory access patterns during probing)
Load Factor Limit	Can exceed $\alpha = 1.0$, but degrades gracefully	Must stay well below $\alpha = 0.8$ to avoid clustering
Deletion Mechanics	Simple hard delete via linked list node unlink and free	Requires soft deletes (tombstones) and delayed cleanup
CPU Cost of Hash	Mitigated by storing uint32_t hash_key in node	Mitigated by storing uint32_t hash_key in slot
Insertion Path	Always traverses chain to enforce uniqueness	Probes until match found or an empty/tombstone slot reached

---

Summary of Key Takeaways

1. Two-Step Hashing: Application objects map to an integer domain ($[0, 2^{32}-1]$), which is then compressed to a bucket index. Key comparisons remain essential because index collisions and hash collisions are unavoidable.
2. Store the 32-bit Hash: Recomputing hashes during set operations is computationally wasteful. Storing the computed integer hash directly inside the node or slot allows fast, short-circuit equality rejections before executing costly string or struct comparators.
3. Decouple Types via Function Pointers: A generic systems implementation requires key_cmp for equality checking and key_destructor for lifecycle cleanup.
4. Set Invariant Cost: Unlike maps that allow blind updates, a hash set must verify whether an element exists before inserting, turning every insertion into an implicit lookup.
5. Open Addressing Tombstones: In open-addressed sets, table capacity management must track both active and deleted slots to prevent performance degradation from tombstone accumulation.