Hash Tables

The previous two lessons measured a value either appearing permanently through a shared object (shared) or passing through a mediator exactly once and disappearing (handoff). This lesson measures a third class, copy: reading a record from a hash table does not remove that record from the table, and does not produce an object shared with the table’s record either — it hands the caller its own copy of the record. A change made on this copy never reaches the table at all, because there is no memory block shared between the two.

Hash Table: Insertion and Lookup with Separate Chaining

The table consists of a fixed number of buckets; each bucket is a linked list (a chain). hash_index maps a key to an index based on the bucket count. hash_insert updates the record if the key already exists in the chain, otherwise adds a new node at the front of the chain. hash_find writes a copy of the record to out and returns 1 if it finds the record; returns 0 if it does not.

// hash.h — hash table with separate chaining
#ifndef HASH_H
#define HASH_H

#define HASH_CAPACITY 8

struct Record {
    int amount;
    int counter;
};

struct HashNode {
    int key;
    struct Record value;
    struct HashNode *next;
};

struct HashTable {
    struct HashNode *buckets[HASH_CAPACITY];
};

void hash_init(struct HashTable *t);
void hash_insert(struct HashTable *t, int key, struct Record value);
int hash_find(const struct HashTable *t, int key, struct Record *out);
void hash_free(struct HashTable *t);

#endif

// hash.c — implementation of the hash table operations
#include <stdlib.h>
#include "hash.h"

static int hash_index(int key) {
    return (key % HASH_CAPACITY + HASH_CAPACITY) % HASH_CAPACITY;
}

void hash_init(struct HashTable *t) {
    for (int i = 0; i < HASH_CAPACITY; i++) {
        t->buckets[i] = NULL;
    }
}

void hash_insert(struct HashTable *t, int key, struct Record value) {
    int i = hash_index(key);
    for (struct HashNode *n = t->buckets[i]; n != NULL; n = n->next) {
        if (n->key == key) {
            n->value = value;
            return;
        }
    }
    struct HashNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return;
    }
    node->key = key;
    node->value = value;
    node->next = t->buckets[i];
    t->buckets[i] = node;
}

int hash_find(const struct HashTable *t, int key, struct Record *out) {
    int i = hash_index(key);
    for (struct HashNode *n = t->buckets[i]; n != NULL; n = n->next) {
        if (n->key == key) {
            *out = n->value;
            return 1;
        }
    }
    return 0;
}

void hash_free(struct HashTable *t) {
    for (int i = 0; i < HASH_CAPACITY; i++) {
        struct HashNode *n = t->buckets[i];
        while (n != NULL) {
            struct HashNode *next = n->next;
            free(n);
            n = next;
        }
    }
}

The Read Record Being Its Own Copy

A record is inserted and then read, then the read copy is changed. The actual measurement is whether the value read again from the table after this change still holds its original value.

// found_copy.c — is the read record changed, does the table stay unaffected
#include <stdio.h>
#include "hash.h"

int main(void) {
    struct HashTable t;
    hash_init(&t);

    struct Record initial = {100, 1};
    hash_insert(&t, 3, initial);

    struct Record found;
    hash_find(&t, 3, &found);
    printf("%s %d\n", "amount first read", found.amount);

    found.amount = 900;
    printf("%s %d\n", "copy's amount after the copy is changed", found.amount);

    struct Record found_again;
    hash_find(&t, 3, &found_again);
    printf("%s %d\n", "amount read again from the table", found_again.amount);

    hash_free(&t);
    return 0;
}

amount first read 100
copy's amount after the copy is changed 900
amount read again from the table 100

DS7. hash_find‘s signature (int hash_find(const struct HashTable *t, int key, struct Record *out)) does not say whether the struct Record written to out is the table’s own record or an independent copy — what decides this is the line *out = n->value, a struct assignment. Assigning one struct to another in C copies its fields one by one; after this assignment, found does not point at the same memory block as n->value — it sits in its own independent block. The assignment found.amount = 900 therefore changes only found; the table parameter is already passed to hash_find as const struct HashTable *, and the function never changes it at all. The second hash_find call reads from the table again and gives back the first value (100) — not 900. The class is copy: a change made on the read record never reaches a second reader (here, the table itself), because there is no object shared between them.

Re-inserting With the Same Key

When hash_insert is called a second time with the same key, it does not add a new node — it updates the existing node’s value field. This does not affect a copy already read earlier — that copy already sits in its own separate memory block.

// reinsertion.c — updating with the same key does not affect a previous copy
#include <stdio.h>
#include "hash.h"

int main(void) {
    struct HashTable t;
    hash_init(&t);

    struct Record initial = {5, 1};
    hash_insert(&t, 7, initial);

    struct Record found_before;
    hash_find(&t, 7, &found_before);
    printf("%s %d\n", "amount read before the update", found_before.amount);

    struct Record updated = {50, 2};
    hash_insert(&t, 7, updated);

    printf("%s %d\n", "old copy's amount after the update", found_before.amount);

    struct Record found_after;
    hash_find(&t, 7, &found_after);
    printf("%s %d\n", "amount read from the table after the update", found_after.amount);

    hash_free(&t);
    return 0;
}

amount read before the update 5
old copy's amount after the update 5
amount read from the table after the update 50

DS8. found_before is a copy taken before the hash_insert(&t, 7, updated) call — since it has no remaining link to the table at all, it does not change when the table is updated; it stays at 5. found_after, read from the table again, sees the current value (50), because this time hash_find was called after the update and took a new copy of the table’s state at that moment. These two lines together show the copy class’s boundary: a copy carries the value it held at the moment it was taken forever; even if its source changes afterward, the copy never sees this, because seeing it would require a shared link between them.

Colliding Keys Chained in the Same Bucket

Since the capacity is eight, keys 3 and 11 fall into the same bucket (3 % 8 = 3, 11 % 8 = 3). In this case hash_insert adds the second node at the front of the chain; hash_find finds the correct key by searching the chain.

// colliding_keys.c — two different keys falling into the same bucket
#include <stdio.h>
#include "hash.h"

int main(void) {
    struct HashTable t;
    hash_init(&t);

    struct Record first = {11, 0};
    struct Record second = {22, 0};
    hash_insert(&t, 3, first);
    hash_insert(&t, 11, second);

    struct Record result;
    hash_find(&t, 3, &result);
    printf("%s %d\n", "amount found for key 3", result.amount);
    hash_find(&t, 11, &result);
    printf("%s %d\n", "amount found for key 11", result.amount);

    hash_free(&t);
    return 0;
}

amount found for key 3 11
amount found for key 11 22

DS9. Even though the two keys fall into the same bucket, hash_find finds the correct record, because the search does not look only at the bucket’s index — it also checks the key field of every node in the chain (n->key == key). This shows why a hash table is not an array but an array of lists: more than one key can fall into the same bucket, and the chain resolves this collision. The collision itself does not change the class this lesson measures — both hash_find calls still each produce their own copy.

A Version That Holds the Key by Pointer

The table so far has held the key as an int, by value — the key passed to hash_insert is copied, and the node stores its own independent copy. A version can also be written that instead holds the key by pointer; this turns the class the key measures from copy to shared, and creates a different hazard.

// hash_ptr.h — declaration of the hash table variant that holds the key by pointer
#ifndef HASH_PTR_H
#define HASH_PTR_H

#include "hash.h"

struct HashNodePtr {
    const int *key;
    struct Record value;
    struct HashNodePtr *next;
};

struct HashTablePtr {
    struct HashNodePtr *buckets[HASH_CAPACITY];
};

void hash_ptr_init(struct HashTablePtr *t);
void hash_ptr_insert(struct HashTablePtr *t, const int *key, struct Record value);
int hash_ptr_find(const struct HashTablePtr *t, int key_value, struct Record *out);
void hash_ptr_free(struct HashTablePtr *t);

#endif

// hash_ptr.c — implementation of the hash table variant that holds the key by pointer
#include <stdlib.h>
#include "hash_ptr.h"

static int hash_ptr_index(int key_value) {
    return (key_value % HASH_CAPACITY + HASH_CAPACITY) % HASH_CAPACITY;
}

void hash_ptr_init(struct HashTablePtr *t) {
    for (int i = 0; i < HASH_CAPACITY; i++) {
        t->buckets[i] = NULL;
    }
}

void hash_ptr_insert(struct HashTablePtr *t, const int *key, struct Record value) {
    int i = hash_ptr_index(*key);
    struct HashNodePtr *node = malloc(sizeof *node);
    if (node == NULL) {
        return;
    }
    node->key = key;
    node->value = value;
    node->next = t->buckets[i];
    t->buckets[i] = node;
}

int hash_ptr_find(const struct HashTablePtr *t, int key_value, struct Record *out) {
    int i = hash_ptr_index(key_value);
    for (struct HashNodePtr *n = t->buckets[i]; n != NULL; n = n->next) {
        if (*(n->key) == key_value) {
            *out = n->value;
            return 1;
        }
    }
    return 0;
}

void hash_ptr_free(struct HashTablePtr *t) {
    for (int i = 0; i < HASH_CAPACITY; i++) {
        struct HashNodePtr *n = t->buckets[i];
        while (n != NULL) {
            struct HashNodePtr *next = n->next;
            free(n);
            n = next;
        }
    }
}

// key_pointer.c — does the lookup break when the variable holding the key later changes
#include <stdio.h>
#include "hash_ptr.h"

int main(void) {
    struct HashTablePtr t;
    hash_ptr_init(&t);

    int key_variable = 5;
    struct Record value = {42, 1};
    hash_ptr_insert(&t, &key_variable, value);

    struct Record found;
    int found_before = hash_ptr_find(&t, 5, &found);
    printf("%s %d\n", "was it found with key 5 before the change", found_before);

    key_variable = 99;

    int found_with_old_value = hash_ptr_find(&t, 5, &found);
    printf("%s %d\n", "found with old value 5 after changing the variable to 99", found_with_old_value);

    int found_with_new_value = hash_ptr_find(&t, 99, &found);
    printf("%s %d\n", "found with new value 99 after changing the variable to 99", found_with_new_value);

    hash_ptr_free(&t);
    return 0;
}

was it found with key 5 before the change 1
found with old value 5 after changing the variable to 99 0
found with new value 99 after changing the variable to 99 0

DS16. hash_ptr_insert computes the node’s bucket from *key — the current value of key_variable at that moment — and this bucket never changes afterward. But the node does not copy the key; it holds the address of key_variable — so there is a shared relationship between the key field and the caller’s variable. When key_variable changes to 99, the memory n->key points at also becomes 99, but the node still sits in the bucket for 5. Result: when searched with 5, the node sitting in the bucket no longer has the key 5 (not found); when searched with 99, the correct bucket (the bucket for 99) is empty (also not found). The record becomes unreachable by any key — placement into a bucket was a one-time decision, but the comparison keeps reading live memory. hash_insert is immune to this hazard, because it copies the key by value; holding the key by pointer loses this protection.

The Bounding Measurement

A lookup function’s return type does not say whether the record it returns is shared with the table’s own memory. The struct Record *out parameter carries a pointer, but where that pointer points is the caller’s own local variable — the table has no knowledge of this variable. Because this lesson’s hash_find always performs a struct assignment (*out = n->value), the class is always copy; a function written with the same signature would give shared as its result if it instead wrote the address of the table’s own node into out (if out were a struct Record **). This difference can only be understood by reading the body, or — as done in this lesson — by changing the source afterward and measuring whether the copy sees it.

Summary

• A hash table distributes into a fixed number of buckets; each bucket is a chain, and colliding keys within the same chain are distinguished by checking the key field.
• hash_find produces a copy of the record through a struct assignment (*out = n->value); a change on the copy never reaches the table — the class is copy.
• A copy keeps carrying the value it held at the moment it was taken; even if the source changes afterward, a copy taken earlier does not see this.
• Copy’s difference from shared: in shared there is a single shared object, in copy there are two independent objects; its difference from handoff: in handoff the read slot empties, in copy the table can hand back the same record again and again (in its current form).
• Whether a lookup function’s returned value is a copy or a shared object does not show up in its signature; it can only be understood by reading the body or by measurement.
• Holding the key by pointer instead of by value turns the class into shared: a bucket’s placement is fixed to the value at insertion time, but the comparison reads live memory — if the outside variable changes, the record can become unreachable by any key.

Next Step

These three lessons measured three separate classes (shared, handoff, copy) through a linked structure, a buffer, and a table. The next lesson, Object-Like Design, looks at how C builds the impression of an “object” in a language without classes — through function pointers and opaque structs — and shows how these three classes can coexist within the same object interface.