---
title: 'Hash Tables'
source: 'https://academia.sh/en/courses/c-systems-programming/hash-tables'
course: 'Systems Programming with C'
language: en
updated: '2026-09-26T03:02:44+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - 'Implements a hash table with separate chaining in C, with insertion, lookup, and release operations'
    - 'Measures that reading a record produces its own copy, without affecting the record in the table'
    - 'Shows how colliding keys chain in the same bucket'
---

# Hash Tables

Measuring that reading a record from a hash table with separate chaining produces its own copy, without changing the record in the table; and how colliding keys chain in the same bucket.

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.

```c
// 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
```

```c
// 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.

```c
// 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.

```c
// 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.

```c
// 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.

```c
// 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
```

```c
// 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;
        }
    }
}
```

```c
// 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.