Hash Tables

A hash table turns key lookup into array access. A hash function transforms a key into a large integer, and the table maps that integer to a bucket or slot. When hashes are well distributed and the table is not overcrowded, insertion, lookup, and deletion take expected constant time.

The word expected matters. Different keys can map to the same position, so every correct hash table needs a collision strategy. Poor hash functions, high load, or adversarial keys—keys deliberately chosen to collide—can produce linear-time operations. A hash table is an engineered combination of hashing, equality, collision resolution, capacity policy, and ownership—not magic constant-time storage.

Dictionary ADT

A dictionary maps unique keys to values:

"Ada"   -> 91
"Linus" -> 84
"Edsger"-> 96

Common operations are:

put(key, value)       insert or replace
get(key, out)         retrieve associated value
contains(key)         test membership
remove(key)           erase an entry
size()                count entries
clear()               erase all entries

The contract must define what put does when the key already exists. This chapter replaces its value and keeps one entry per equal key.

Dictionary iteration order is normally unspecified. Resizing or deletion may change it. If insertion order or sorted order matters, the structure must preserve that order separately.

Set ADT

A set stores unique keys without associated client values:

add(key)
contains(key)
remove(key)

A set can use dictionary machinery with a dummy value, but a dedicated representation may omit value storage. Set operations such as union and intersection iterate keys and perform membership queries; they are not the same as disjoint-set union, which maintains a partition and appears in the next chapter.

Hash Functions

A hash function maps a key from a large domain into a fixed-width integer:

hash: Keys -> {0, 1, ..., 2^w - 1}

The table then derives a position, often with:

index = hash(key) mod capacity

For power-of-two capacity, hash & (capacity - 1) is equivalent to modulo only when capacity is positive and a power of two. The hash’s low bits must then be well mixed.

Determinism

Within one table operation history, equal keys must produce equal hashes. If a key changes while stored and its hash changes, lookup searches the wrong location. Keys should be immutable with respect to hashing and equality while resident.

Distribution

A useful hash spreads realistic keys across the output range. It should use every relevant key component and avoid preserving obvious input patterns in the bits used for bucket selection.

Uniform distribution is a workload property, not a visual promise. A function can distribute random keys well and perform badly on sequential IDs, common string prefixes, or adversarial inputs.

Speed

Hashing occurs on every core operation. It should usually take time proportional to key length. For strings, claiming table lookup is O(1) treats key length as bounded; a more precise cost is expected O(length(key) + collision work).

Integer Hashing

For small integer keys that are already well distributed, reducing by capacity may suffice:

size_t index = (size_t)key % capacity;

Signed negative keys require careful conversion or a mixing function. Casting a signed integer to an unsigned type is well-defined modulo the unsigned range, after which bit mixing can spread patterns.

One 64-bit finalizer is:

#include <stdint.h>

static uint64_t mix_u64(uint64_t x) {
    x ^= x >> 30;
    x *= UINT64_C(0xbf58476d1ce4e5b9);
    x ^= x >> 27;
    x *= UINT64_C(0x94d049bb133111eb);
    x ^= x >> 31;
    return x;
}

This is a non-cryptographic mixer. It improves distribution for patterns; it does not provide authentication or resistance to a determined attacker who knows the function.

String Hashing

A string hash consumes every byte in sequence. FNV-1a is compact enough to study:

static uint64_t hash_string(const char *text) {
    uint64_t hash = UINT64_C(14695981039346656037);
    while (*text != '\0') {
        hash ^= (unsigned char)*text++;
        hash *= UINT64_C(1099511628211);
    }
    return hash;
}

Changing one character typically changes many result bits after repeated multiplication. FNV-1a is not cryptographic and is not automatically safe for attacker-controlled hash-table keys. Security-sensitive runtimes often use a keyed, randomized function.

Hash caching

If long immutable keys are probed repeatedly, entries can store their already computed hash. Lookup first compares hashes, then performs full equality only when hashes match. Cached hashes consume memory but can reduce repeated string work and accelerate rehashing.

Key Equality

Hashing narrows candidates; equality makes the final decision.

The required consistency rule is:

equal(a, b) implies hash(a) == hash(b)

The reverse is not required. Two unequal keys may share a hash.

If strings are compared case-insensitively, hashing must also normalize case equivalently. If equality ignores punctuation but hashing includes it, an equal key may live in a different probe sequence and become unreachable.

For composite keys, equality and hashing must cover the same fields. Mutable fields used by either function should not change while the key is stored.

Collisions

A collision occurs when different keys map to the same initial position. Collisions are inevitable when the key domain is larger than the table because of the pigeonhole principle.

hash("Ada")   mod 8 = 3
hash("Grace") mod 8 = 3

Correctness does not depend on avoiding all collisions. Performance depends on distributing them and resolving them efficiently.

Two major strategies are:

• separate chaining: each bucket stores a collection of entries;
• open addressing: every entry occupies a slot in the table array, and collisions probe other slots.

Separate Chaining

An array stores one chain head per bucket:

bucket 0: NULL
bucket 1: ["Ken", 77] -> NULL
bucket 2: NULL
bucket 3: ["Grace", 92] -> ["Ada", 91] -> NULL
bucket 4: ["Linus", 84] -> NULL

typedef struct Entry {
    char *key;
    int value;
    uint64_t hash;
    struct Entry *next;
} Entry;

typedef struct {
    Entry **buckets;
    size_t capacity;
    size_t size;
} ChainedMap;

Chaining invariant

• every entry belongs to exactly one bucket;
• an entry with hash h belongs to h % capacity;
• no two entries contain equal keys;
• following next reaches each bucket entry exactly once and terminates;
• the sum of chain lengths equals size;
• the map owns every entry and, under a copying-key policy, every entry key.

Lookup

Compute the hash, select one bucket, then compare candidates in its chain:

Entry *entry = map->buckets[hash % map->capacity];
while (entry != NULL) {
    if (entry->hash == hash && strcmp(entry->key, key) == 0) {
        return entry;
    }
    entry = entry->next;
}

Comparing cached hashes before strings rejects most collisions cheaply.

Chain insertion

If an equal key exists, replace its value. Otherwise allocate an entry and prepend it to the bucket. Allocate and copy the key before changing the chain head so failure leaves the table unchanged.

Chain deletion

Keep previous and current, unlink the matching entry, release its owned key and record, and decrement size. Deleting the bucket head is the boundary case where the bucket array itself holds the incoming link.

Bucket alternatives

Buckets need not be linked lists. They may use dynamic arrays for locality, balanced trees for adversarial worst-case bounds, or small inline arrays that spill only when collisions grow. The outer hashing scheme and inner bucket representation are separate decisions.

Chaining Program

This small C17 map uses eight fixed buckets and integer keys so collision handling remains visible. Keys 1, 9, and 17 deliberately enter the same bucket. The table owns its entry nodes, put replaces an existing value without allocation, and allocation failure while inserting a new key leaves the map unchanged. A production table would normally mix keys more thoroughly and resize its bucket array as load grows.

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

enum { CHAIN_BUCKETS = 8 };

typedef struct ChainEntry {
    int key;
    int value;
    struct ChainEntry *next;
} ChainEntry;

typedef struct {
    ChainEntry *buckets[CHAIN_BUCKETS];
    size_t size;
} ChainMap;

typedef enum {
    CHAIN_INSERTED,
    CHAIN_REPLACED,
    CHAIN_NO_MEMORY
} ChainPutStatus;

static size_t chain_bucket(int key) {
    uint32_t bits = (uint32_t)key;
    return (size_t)(bits % CHAIN_BUCKETS);
}

static void chain_map_init(ChainMap *map) {
    for (size_t i = 0; i < CHAIN_BUCKETS; i++) {
        map->buckets[i] = NULL;
    }
    map->size = 0;
}

static ChainPutStatus chain_map_put(ChainMap *map, int key, int value) {
    size_t bucket = chain_bucket(key);
    for (ChainEntry *entry = map->buckets[bucket];
         entry != NULL;
         entry = entry->next) {
        if (entry->key == key) {
            entry->value = value;
            return CHAIN_REPLACED;
        }
    }

    ChainEntry *entry = malloc(sizeof *entry);
    if (entry == NULL) {
        return CHAIN_NO_MEMORY;
    }

    entry->key = key;
    entry->value = value;
    entry->next = map->buckets[bucket];
    map->buckets[bucket] = entry;
    map->size++;
    return CHAIN_INSERTED;
}

static bool chain_map_get(const ChainMap *map, int key, int *out) {
    if (out == NULL) {
        return false;
    }

    size_t bucket = chain_bucket(key);
    for (const ChainEntry *entry = map->buckets[bucket];
         entry != NULL;
         entry = entry->next) {
        if (entry->key == key) {
            *out = entry->value;
            return true;
        }
    }
    return false;
}

static bool chain_map_remove(ChainMap *map, int key) {
    size_t bucket = chain_bucket(key);
    ChainEntry **link = &map->buckets[bucket];

    while (*link != NULL && (*link)->key != key) {
        link = &(*link)->next;
    }
    if (*link == NULL) {
        return false;
    }

    ChainEntry *victim = *link;
    *link = victim->next;
    free(victim);
    map->size--;
    return true;
}

static void chain_map_print(const ChainMap *map) {
    for (size_t bucket = 0; bucket < CHAIN_BUCKETS; bucket++) {
        const ChainEntry *entry = map->buckets[bucket];
        if (entry == NULL) {
            continue;
        }

        printf("bucket %zu:", bucket);
        while (entry != NULL) {
            printf(" (%d,%d)", entry->key, entry->value);
            entry = entry->next;
        }
        putchar('\n');
    }
}

static void chain_map_destroy(ChainMap *map) {
    for (size_t bucket = 0; bucket < CHAIN_BUCKETS; bucket++) {
        ChainEntry *entry = map->buckets[bucket];
        while (entry != NULL) {
            ChainEntry *next = entry->next;
            free(entry);
            entry = next;
        }
        map->buckets[bucket] = NULL;
    }
    map->size = 0;
}

int main(void) {
    ChainMap map;
    chain_map_init(&map);

    if (chain_map_put(&map, 1, 10) == CHAIN_NO_MEMORY ||
        chain_map_put(&map, 9, 90) == CHAIN_NO_MEMORY ||
        chain_map_put(&map, 17, 170) == CHAIN_NO_MEMORY ||
        chain_map_put(&map, 2, 20) == CHAIN_NO_MEMORY) {
        chain_map_destroy(&map);
        return EXIT_FAILURE;
    }

    chain_map_put(&map, 9, 99);       /* replace, no new node */
    int value;
    if (chain_map_get(&map, 9, &value)) {
        printf("key 9 -> %d\n", value);
    }

    chain_map_remove(&map, 1);
    chain_map_print(&map);
    printf("size=%zu\n", map.size);

    chain_map_destroy(&map);
    return EXIT_SUCCESS;
}

Expected output:

key 9 -> 99
bucket 1: (17,170) (9,99)
bucket 2: (2,20)
size=3

The pointer-to-pointer variable link in removal identifies the link that leads to the current entry. It begins at the bucket head and later may refer to a node’s next field, so deleting the first or a later chain entry uses one update rule.

Open Addressing

Open addressing stores entries directly in the table. On collision, a probe sequence examines alternative slots:

probe(key, 0), probe(key, 1), probe(key, 2), ...

Every key must use the same probe sequence during lookup that insertion used. Lookup stops when it finds the key or a truly empty slot.

Each slot needs a state:

typedef enum {
    SLOT_EMPTY,
    SLOT_OCCUPIED,
    SLOT_DELETED
} SlotState;

An empty slot has never held an entry in the current probe history. A deleted slot held one but now contains a tombstone. They cannot be treated identically during lookup.

Open-address invariant

• each occupied slot owns one key-value entry;
• no two occupied slots have equal keys;
• every occupied key is reachable along its probe sequence before the first empty slot;
• size counts occupied slots;
• tombstones counts deleted slots;
• all remaining slots are empty.

The table must retain at least one usable stopping condition; implementations usually resize before every slot is occupied or deleted.

Linear Probing

Linear probing uses:

Change the keys and table size below, then compare linear, quadratic, and double-hash probe sequences. The exact collision count makes clustering visible rather than merely descriptive.

probe(h, i) = (h + i) mod capacity

For capacity 8 and initial index 3:

3, 4, 5, 6, 7, 0, 1, 2

It has excellent cache locality because probes visit neighboring slots. Its weakness is primary clustering: contiguous occupied runs grow, and any key hashing into the run extends or traverses it.

Trace insertions whose initial index is 3:

insert A: slot 3
insert B: 3 occupied -> slot 4
insert C: 3,4 occupied -> slot 5

[__, __, __, A, B, C, __, __]

Now a key whose initial index is 4 joins the same cluster.

Quadratic Probing

Quadratic probing spaces later probes using a quadratic term:

probe(h, i) = (h + c1*i + c2*i*i) mod capacity

It reduces primary clustering because colliding keys do not simply grow one contiguous run. Keys with the same initial hash still follow the same sequence, causing secondary clustering.

Not every capacity and coefficient combination visits every slot. The capacity policy and probe formula must be designed together; otherwise insertion can fail despite empty slots.

Double Hashing

Double hashing derives a step from a second hash:

probe(h1, h2, i) = (h1 + i * h2) mod capacity

The step must be nonzero and relatively prime to capacity so the sequence can visit every slot. For power-of-two capacity, forcing the step odd ensures coprimality:

step = (second_hash(key) | 1)

Different keys with the same initial slot can take different paths, reducing clustering. Double hashing costs more hash computation and produces less sequential memory access than linear probing.

Tombstones

Consider a linear-probing cluster:

index:  3  4  5  6
entry:  A  B  C  empty

Suppose all three keys initially hash to 3. If B is removed by making slot 4 empty, lookup for C stops at 4 and incorrectly reports absence.

Mark slot 4 deleted instead:

entry: A  tombstone  C  empty

Lookup continues through tombstones. Insertion remembers the first tombstone but keeps probing to check whether the key already exists later. It may reuse that first tombstone only after reaching an empty slot or finding no duplicate in the complete permitted probe sequence.

Too many tombstones lengthen probes even when size is small. Rehashing into a fresh array removes them.

Load Factors

Load factor measures occupancy relative to capacity.

For chaining:

alpha = entries / buckets

alpha may exceed 1; average chain length grows with it under uniform hashing.

For open addressing:

alpha = occupied slots / total slots

It must remain below 1, and performance deteriorates sharply as it approaches 1. A practical resize trigger often considers both occupied slots and tombstones:

(size + tombstones) / capacity

The exact threshold is an engineering choice. Linear probing commonly grows around 0.6–0.8 load, trading memory for shorter probe runs.

Clustering

Clustering is not merely multiple keys sharing an exact hash. It is the formation of probe patterns that interact and create long searches.

• primary clustering: linear-probing runs merge and attract more keys;
• secondary clustering: keys with the same initial position share a probe sequence;
• poor bit distribution: power-of-two masking overuses some slots;
• tombstone buildup: deleted positions extend searches.

Probe-length histograms reveal clustering more directly than load factor alone.

Table Resizing

Growing an open-addressed table requires re-inserting entries into a fresh slot array because positions depend on capacity.

old index = hash % old_capacity
new index = hash % new_capacity

Copying entries to the same numeric indices would make many keys unreachable under their new probe sequences.

For chaining, bucket index also changes with capacity, so each entry must move to its new bucket even though node allocations may be reused.

Rehashing

Rehashing means constructing collision structure again under the current or new capacity. It can:

• grow the table;
• shrink an underused table;
• remove tombstones without changing capacity;
• adopt a new randomized seed after suspicious collisions.

Allocate the new outer storage before mutating the old table. If allocation fails, retain the original valid table.

Geometric growth makes resize cost amortized across many insertions. A single put may still cost linear time, which matters for strict-latency systems.

Open-Address Program

This complete C17 map uses copied string keys, integer values, FNV-1a hashing, power-of-two capacity, linear probing, tombstones, and geometric rehashing. put replaces an existing value and reports allocation failure without losing existing entries.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {
    SLOT_EMPTY,
    SLOT_OCCUPIED,
    SLOT_DELETED
} SlotState;

typedef struct {
    char *key;
    int value;
    uint64_t hash;
    SlotState state;
} Entry;

typedef struct {
    Entry *slots;
    size_t capacity;
    size_t size;
    size_t tombstones;
} StringMap;

static uint64_t hash_string(const char *text) {
    uint64_t hash = UINT64_C(14695981039346656037);
    while (*text != '\0') {
        hash ^= (unsigned char)*text++;
        hash *= UINT64_C(1099511628211);
    }
    return hash;
}

static char *copy_string(const char *source) {
    size_t length = strlen(source);
    if (length == SIZE_MAX) {
        return NULL;
    }
    char *copy = malloc(length + 1);
    if (copy != NULL) {
        memcpy(copy, source, length + 1);
    }
    return copy;
}

void map_init(StringMap *map) {
    map->slots = NULL;
    map->capacity = 0;
    map->size = 0;
    map->tombstones = 0;
}

void map_destroy(StringMap *map) {
    for (size_t i = 0; i < map->capacity; ++i) {
        if (map->slots[i].state == SLOT_OCCUPIED) {
            free(map->slots[i].key);
        }
    }
    free(map->slots);
    map_init(map);
}

static size_t find_slot(const StringMap *map, const char *key,
                        uint64_t hash, bool *found) {
    size_t mask = map->capacity - 1;
    size_t first_deleted = SIZE_MAX;

    for (size_t probe = 0; probe < map->capacity; ++probe) {
        size_t index = ((size_t)hash + probe) & mask;
        const Entry *entry = &map->slots[index];

        if (entry->state == SLOT_EMPTY) {
            *found = false;
            return first_deleted == SIZE_MAX ? index : first_deleted;
        }
        if (entry->state == SLOT_DELETED) {
            if (first_deleted == SIZE_MAX) {
                first_deleted = index;
            }
        } else if (entry->hash == hash && strcmp(entry->key, key) == 0) {
            *found = true;
            return index;
        }
    }

    *found = false;
    return first_deleted;
}

static void insert_moved(StringMap *map, Entry entry) {
    bool found;
    size_t index = find_slot(map, entry.key, entry.hash, &found);
    assert(!found && index != SIZE_MAX);
    map->slots[index] = entry;
    map->slots[index].state = SLOT_OCCUPIED;
    ++map->size;
}

static bool map_rehash(StringMap *map, size_t capacity) {
    assert(capacity >= 16 && (capacity & (capacity - 1)) == 0);
    if (capacity > SIZE_MAX / sizeof *map->slots) {
        return false;
    }

    Entry *new_slots = calloc(capacity, sizeof *new_slots);
    if (new_slots == NULL) {
        return false;
    }

    StringMap fresh = {
        .slots = new_slots,
        .capacity = capacity,
        .size = 0,
        .tombstones = 0
    };

    for (size_t i = 0; i < map->capacity; ++i) {
        if (map->slots[i].state == SLOT_OCCUPIED) {
            insert_moved(&fresh, map->slots[i]);
        }
    }

    free(map->slots);
    *map = fresh;
    return true;
}

static bool ensure_insert_room(StringMap *map) {
    if (map->capacity == 0) {
        return map_rehash(map, 16);
    }

    size_t used = map->size + map->tombstones;
    if (used + 1 <= map->capacity * 7 / 10) {
        return true;
    }

    if (map->size + 1 <= map->capacity * 4 / 10) {
        return map_rehash(map, map->capacity); /* clear tombstones */
    }
    if (map->capacity > SIZE_MAX / 2) {
        return false;
    }
    return map_rehash(map, map->capacity * 2);
}

bool map_put(StringMap *map, const char *key, int value) {
    if (key == NULL || !ensure_insert_room(map)) {
        return false;
    }

    uint64_t hash = hash_string(key);
    bool found;
    size_t index = find_slot(map, key, hash, &found);
    assert(index != SIZE_MAX);

    if (found) {
        map->slots[index].value = value;
        return true;
    }

    char *owned_key = copy_string(key);
    if (owned_key == NULL) {
        return false;
    }

    if (map->slots[index].state == SLOT_DELETED) {
        --map->tombstones;
    }
    map->slots[index] = (Entry){
        .key = owned_key,
        .value = value,
        .hash = hash,
        .state = SLOT_OCCUPIED
    };
    ++map->size;
    return true;
}

bool map_get(const StringMap *map, const char *key, int *out) {
    if (key == NULL || out == NULL || map->capacity == 0) {
        return false;
    }
    uint64_t hash = hash_string(key);
    bool found;
    size_t index = find_slot(map, key, hash, &found);
    if (!found) {
        return false;
    }
    *out = map->slots[index].value;
    return true;
}

bool map_remove(StringMap *map, const char *key) {
    if (key == NULL || map->capacity == 0) {
        return false;
    }
    uint64_t hash = hash_string(key);
    bool found;
    size_t index = find_slot(map, key, hash, &found);
    if (!found) {
        return false;
    }

    free(map->slots[index].key);
    map->slots[index].key = NULL;
    map->slots[index].state = SLOT_DELETED;
    --map->size;
    ++map->tombstones;
    return true;
}

int main(void) {
    StringMap scores;
    map_init(&scores);

    if (!map_put(&scores, "Ada", 91) ||
        !map_put(&scores, "Grace", 92) ||
        !map_put(&scores, "Edsger", 96) ||
        !map_put(&scores, "Ada", 95)) {
        map_destroy(&scores);
        return EXIT_FAILURE;
    }

    int score;
    if (map_get(&scores, "Ada", &score)) {
        printf("Ada: %d\n", score); /* 95 */
    }
    map_remove(&scores, "Grace");
    printf("entries: %zu\n", scores.size); /* 2 */
    map_destroy(&scores);
    return EXIT_SUCCESS;
}

The length == SIZE_MAX check in copy_string protects length + 1, although no valid C string object can practically reach that size on ordinary systems. The code retains it to make the allocation arithmetic explicit.

calloc initializes enum storage to zero, and SLOT_EMPTY is deliberately the zero enumerator. Relying on that relationship should be documented as part of the representation.

Expected Costs

Under uniform hashing and controlled load:

For string keys, add hashing and equality work proportional to examined key bytes.

Expected constant time depends on an assumption about hash distribution or randomization. It is not a worst-case bound for an arbitrary deterministic function and arbitrary keys.

Worst-Case Costs

If every key collides:

• chaining builds one chain of length n;
• open addressing builds a probe sequence of length n;
• lookup, insertion, and deletion become Theta(n).

Balanced-tree buckets can bound chaining lookup by O(log n) after a collision threshold, but add code and per-bucket overhead. A cryptographically keyed hash can make deliberate collision construction difficult, but security requirements should use a reviewed design rather than an educational hash.

Collision Attacks

When external users choose keys, an attacker may submit many colliding inputs and turn expected constant operations into repeated linear work. This can create denial of service.

Defenses include:

• a per-process or per-table secret seed;
• a keyed hash designed for hash-table use;
• collision-length monitoring and reseeding;
• tree-based buckets;
• input quotas and time limits.

Randomly choosing capacity alone does not necessarily fix a weak, known hash. The function and threat model matter.

Choosing Lookup

Ordered search trees

A balanced search tree guarantees logarithmic operations and preserves key order. A hash table offers expected constant exact lookup but no natural predecessor, successor, or range iteration.

Sorted lookup arrays

Sorted arrays give compact ordered iteration and logarithmic search, but updates shift elements. Hash tables favor frequent unordered updates and exact lookup.

Direct addressing

If keys are dense integers from a small range, an array indexed directly by key can outperform hashing and avoid collisions. Hashing is useful when the key universe is large or sparse.

Tries

Tries navigate keys by characters or bits and support prefix queries. Their cost depends on key length rather than entry count, but node overhead can be high. Hash tables are usually simpler for exact whole-key lookup.

Entry Contracts

put(key, value) hides several decisions that become important as soon as keys or values own memory. A precise copying-map contract might say:

new key:
    copy key, copy/store value, increase size, return INSERTED

equal existing key:
    keep canonical stored key, replace value, return REPLACED

allocation failure:
    preserve all entries and ownership, return NO_MEMORY

Keeping the existing stored key matters when equality is broader than byte identity. If "Ada" and "ADA" compare equal, a replacement can retain the original spelling while updating only the score. Another map may deliberately replace the presentation spelling. Both are valid, but clients should not have to infer which one happened.

A pointer-owning map needs destruction and replacement callbacks. Suppose the map already owns record old under key k, and the caller offers new:

• on successful replacement, destroy old and take ownership of new;
• on failure, preserve old and leave ownership of new with the caller;
• on removal, either destroy the value or return it and transfer ownership out.

Destroying old before all fallible replacement work completes can lose data. Allocate or copy the new representation first, publish it second, and only then release the displaced object.

Returning distinct statuses is more informative than a Boolean:

typedef enum {
    MAP_INSERTED,
    MAP_REPLACED,
    MAP_NO_MEMORY,
    MAP_LIMIT_REACHED
} MapStatus;

size increases only for MAP_INSERTED. A replacement may change the value but must not create another equal key.

Key Normalization

Equality and hashing should come from one key interpretation. Consider usernames where ASCII letter case and surrounding spaces are ignored:

" Ada "  == "ada"

There are two common designs.

Normalize on insertion. Convert the key to a canonical form such as "ada", store that form, and use ordinary byte hashing and equality. Lookup normalizes the query temporarily. This simplifies entry comparison and makes the stored key predictable, at the cost of temporary storage or a streaming normalizer.

Normalize during both operations. A case-folding hash consumes normalized bytes without allocating, and equality performs the same folding while comparing. This can preserve the original spelling, but duplicated rules are easier to make inconsistent.

The dangerous design hashes raw bytes but compares normalized text:

hash("Ada") != hash("ada")
equal("Ada", "ada") == true

The second spelling begins in a different bucket or probe sequence and may never meet the first. The table can then contain two keys that its own equality calls equal.

Unicode normalization and case folding are more complicated than converting ASCII with tolower. They can change byte length and depend on a defined standard. For a course implementation, state an ASCII-only rule or use a reviewed text library; do not claim general Unicode behavior from a byte loop.

Composite keys follow the same principle. For (department, student_id), if equality uses both fields, hashing must combine both. If equality ignores a display name, the hash must ignore it too. Changing any participating field while the key is stored makes the entry unreachable under its old placement.

Probe Termination

An open-address lookup must have a reason to stop. Under linear probing, it stops when one of these occurs:

1. an occupied slot contains an equal key—found;
2. an empty slot appears—the key was never inserted beyond this point;
3. every slot in the permitted probe sequence has been examined—not found.

The third rule is essential in a table containing no empty slots, perhaps because every non-occupied slot is a tombstone. Code that loops until it sees SLOT_EMPTY would run forever.

A bounded loop makes progress explicit:

for (size_t attempt = 0; attempt < capacity; attempt++) {
    size_t index = (start + attempt) % capacity;
    /* inspect slot[index] */
}

For arbitrary probe formulas, capacity attempts are enough only when the formula is designed to visit each possible slot without premature repetition. Double hashing needs a step relatively prime to capacity. A badly chosen step of 2 in capacity 8 visits only four positions:

start 1: 1, 3, 5, 7, 1, ...

Insertion has an additional obligation. It remembers the first tombstone but continues probing for an equal key. On reaching a true empty slot, it inserts at the remembered tombstone if one exists, otherwise at the empty slot. If the bounded sequence ends without empty but a tombstone was remembered, that tombstone is available. If neither exists, the table is full under that probe policy and must grow or report failure.

Modulo arithmetic also deserves care. (start + attempt) % capacity can overflow before the modulo for extreme size_t values. Linear probing can increment an index and wrap explicitly:

index++;
if (index == capacity) {
    index = 0;
}

Capacity zero must be rejected before any modulo operation.

Tombstone Load

An open-addressed table has two useful load measures:

live load     = size / capacity
occupied load = (size + tombstones) / capacity

Live load describes useful data. Occupied load predicts how soon a probe finds a truly empty stopping slot. A table with capacity 16, size 3, and 12 tombstones has low live load but terrible probe behavior:

live load     = 3/16
occupied load = 15/16

Growing merely because occupied load is high may waste memory when the live set is small. Rehashing at the same capacity discards tombstones and changes occupied load back to 3/16. A practical policy distinguishes:

many live entries:       grow and rehash
few live, many deleted:  clean at same capacity
very few live entries:   optionally shrink with hysteresis

Trace a cluster to understand the counters:

capacity 8, size 3, tombstones 0
[__, A, B, C, __, __, __, __]

remove B:
capacity 8, size 2, tombstones 1
[__, A, X, C, __, __, __, __]    X is deleted

insert D through the same cluster, reuse X:
capacity 8, size 3, tombstones 0
[__, A, D, C, __, __, __, __]

Replacing an existing key changes neither counter. Removing an absent key changes neither. Counter assertions around every slot-state transition catch many bugs more cheaply than waiting for a failed lookup.

Backward-shift deletion is an alternative for linear probing: move later entries backward when their legal probe intervals permit it, leaving a true empty slot at the end. This avoids tombstones but requires subtle wraparound reasoning. Tombstones are usually the clearer first implementation.

Rehash Transaction

Rehashing touches every entry, so partial publication is risky. A failure-safe open-address rehash follows this pattern:

1. validate the requested capacity and byte multiplication;
2. allocate a fresh empty slot array;
3. place each live old entry into its new probe sequence;
4. verify the new live count;
5. replace the table’s slot pointer and capacity;
6. release the old slot array.

When keys are already owned by entries, moving their pointers into the new slot array need not copy the strings. Until commit, however, both arrays temporarily refer to those same keys. Failure cleanup must free only the new outer array, not the keys still owned by the old table.

This distinction is easier if a private placement routine cannot allocate and cannot invoke public load checks. It inserts one already-owned entry into a known-empty destination table. Public put and internal rehash_place have different contracts even though both search a probe sequence.

For chaining, new bucket allocation may be the only fallible step. After it succeeds, existing nodes can be relinked into new buckets without allocating. Save each node’s next before changing it:

next = entry->next
prepend entry to new bucket
entry = next

The commit point is the moment the table publishes the new buckets and capacity. size stays unchanged; open addressing resets tombstones to zero. If a randomized hash seed changes, cached hashes must be recomputed unless they represent an unseeded base hash that is mixed with the table seed later.

Table Iteration

Scanning a hash table exposes storage order, not a logical key order. For chaining, iteration walks bucket indices and then chains. For open addressing, it scans slots and skips empty and deleted states. Rehashing can change the order even when the key-value set is identical.

An iterator can store a table version. Structural insertion, successful removal, clear, and rehash increment the version. Before yielding each entry, the iterator compares its saved version with the table’s current version and reports invalidation on mismatch. This prevents following a chain node that removal freed or a slot array that rehash released.

Whether replacing only a value invalidates iteration depends on the interface. If the iterator returns mutable entry pointers, even nonstructural replacement may surprise it. Returning copied keys/values or invoking a callback while mutation is forbidden produces a simpler contract.

Never let a callback mutate the same table unless the iteration API explicitly supports it. A callback-triggered resize can invalidate the loop’s current slot pointer. One safe pattern records keys to modify in a separate collection, finishes iteration, then applies mutations.

If deterministic output matters—for tests, file formats, or user interfaces—collect live keys and sort them, or maintain a separate order structure. Depending on current bucket order accidentally turns capacity and hash seed into public behavior.

Differential Testing

A small unsorted vector of key-value pairs is a slow but transparent oracle. For each random put, get, and remove, compare status and visible value against the vector. Periodically compare the complete key set independent of iteration order.

The generated workload should deliberately include:

• equal keys with different source buffers;
• long collision clusters and wraparound at the final slot;
• replacement before and after tombstones;
• absent lookups that cross tombstones;
• growth, same-size cleanup, and optional shrink;
• capacities and sizes around every threshold;
• copied keys whose caller buffer is changed after insertion.

After each mutation, count slot states, verify size and tombstones, and prove reachability: start from each occupied entry’s initial index and confirm that its probe sequence reaches the entry before any empty slot. For chaining, verify the correct bucket, terminating links, unique keys, and total chain count.

A controlled allocator should fail key copying, entry allocation, bucket creation, and rehash storage one point at a time. Compare a snapshot taken before the call with the state afterward. This tests the promised failure transaction, not just whether code returned an error.

Hash-table tests must not assume iteration order, particularly when randomized hashing is enabled. Compare sets or sort snapshots first. Sanitizers complement invariants by detecting freed key access, chain double-free, and writes beyond a slot array.

Hashing Hazards

Inconsistent equality

Equal keys with different hashes can coexist or become unreachable. Derive both operations from the same normalization rules.

Mutable keys

Changing a stored key’s hash-relevant bytes leaves it in the old probe or bucket location. Copy immutable keys or prohibit mutation until removal.

Empty deletion

Turning a removed open-addressed slot into empty breaks searches for later collided entries. Use a tombstone or a correct cluster-repair deletion algorithm.

Premature tombstone reuse

Stopping at the first tombstone during insertion can create a duplicate if the equal key appears later in the probe sequence. Remember the tombstone, but continue searching.

Missing rehash

Growing the slot array without reinserting entries changes their legal positions and makes lookups fail.

Incorrect ownership

Storing a borrowed pointer to a temporary string makes the key dangle. Copy keys or document a lifetime requirement that clients can actually satisfy.

Unchecked capacity arithmetic

Capacity multiplication and load-threshold arithmetic can overflow. Bound allocations and growth before committing changes.

Accidental iteration contract

Tests that depend on current slot order make harmless rehashing look like a semantic break. Promise order only if the data structure deliberately maintains it.

Table Validation

Use keys selected for structural behavior:

1. empty lookup and removal;
2. first insertion and replacement;
3. keys colliding at one initial slot;
4. a cluster that wraps across the final slot;
5. removal from the beginning, middle, and end of a cluster;
6. lookup through several tombstones;
7. reuse of tombstones without duplicate creation;
8. growth with every key still retrievable;
9. zero and high tombstone load;
10. allocation failure during key copy and during rehash;
11. case or normalization rules for equality;
12. adversarial collision sets.

Maintain a simple reference vector or ordered map during randomized testing and compare every visible key-value pair after each operation.

Hashing Essentials

• A dictionary maps unique keys to values; a set stores unique keys alone.
• Hashing selects candidate storage, while equality confirms identity.
• Equal keys must hash equally, and stored keys must remain hash-stable.
• Collisions are unavoidable and require chaining or probing.
• Linear, quadratic, and double hashing make different locality and clustering trade-offs.
• Tombstones preserve probe reachability after deletion but accumulate search cost.
• Load-factor policy controls expected probe or chain length.
• Resizing requires rehashing every live entry under the new capacity.
• Expected constant time depends on distribution assumptions and can degrade to linear time.
• Ownership, failure guarantees, iteration order, and adversarial inputs belong in the public design.

Hashing Problems

Hashing Rules

1. State the consistency rule connecting hashing and equality.
2. Distinguish an empty open-addressed slot from a tombstone.
3. Why may chaining load factor exceed one while open-addressing load factor may not?
4. Distinguish primary and secondary clustering.

Collision Traces

5. Insert six keys with the same initial index into capacity eight using linear probing, then remove the second and locate the sixth.
6. Repeat with a specified quadratic formula and identify which slots are never visited.
7. Rehash a wrapped cluster from capacity eight to sixteen.
8. Trace a chaining table through head, middle, and final-node deletion in one bucket.

Probe Failures

9. Construct a lookup failure caused by replacing a removed slot with empty.
10. Show how immediate tombstone reuse can create duplicate equal keys.
11. Diagnose a case-insensitive equality function paired with a case-sensitive hash.
12. Explain why changing only capacity after realloc does not resize a hash table correctly.

Table Operations

13. Add contains, clear, and iteration callbacks to the reference implementation.
14. Implement shrinking with a lower threshold that avoids resize thrashing.
15. Implement separate chaining with copied string keys and cached hashes.
16. Replace linear probing with double hashing while retaining power-of-two capacity.
17. Add a debug validator that verifies counts and reachability of every occupied slot.

Hashing Choices

18. Define hash and equality functions for a student key consisting of institution code and numeric ID.
19. Choose chaining or open addressing for large fixed-size records and justify cache, load, and movement costs.
20. Define ownership for keys and values when put replaces an existing dictionary entry.
21. Design a deterministic iteration-order layer without weakening expected lookup complexity.

Deletion and Seeding

22. Implement backward-shift deletion for linear probing and prove which probe invariants it preserves.
23. Measure probe-length distributions at several loads for uniform and patterned keys.
24. Add a randomized seed to string hashing and design tests that remain valid across iteration-order changes.