C Academy · Lesson

Collision Handling

Chaining and probing.

Collision Handling is a free C Academy lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

The Collision Problem

A collision happens when two distinct keys hash to the same bucket. Since collisions are unavoidable, every hash table needs a strategy to store multiple keys in one slot.

The two main families are chaining and open addressing.

Separate Chaining

With separate chaining, each bucket holds a linked list of entries. On collision you simply append (or prepend) to that bucket's list.

Buckets store list heads
Lookups walk one short list

Chaining Node Structure

Each node stores a key, a value, and a next pointer. The table is an array of node pointers.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

Inserting With Chaining

Prepending to the bucket list is O(1). Here we build a tiny chain by hand and print it.

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

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

Open Addressing

With open addressing, every entry lives directly in the bucket array. On collision you probe for another empty slot using a fixed sequence.

No extra nodes are allocated, which is cache-friendly.

Linear Probing

Linear probing checks the next slot, then the next, wrapping around: (h + i) % capacity.

It is simple and cache-friendly but suffers from clustering.

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

Quadratic Probing

Quadratic probing uses (h + i*i) % capacity to spread probes out and reduce primary clustering.

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

Double Hashing

Double hashing uses a second hash for the step size: (h1 + i*h2) % capacity. This gives each key its own probe sequence and the best distribution of the three.

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

Deletion in Open Addressing

You cannot just clear a slot in open addressing, because that would break probe chains for other keys. Instead mark it with a tombstone so lookups keep probing past it.

Chaining vs Open Addressing

Trade-offs:

Chaining: handles high load factors, simple deletes, but uses pointers and allocations
Open addressing: cache-friendly, no per-entry allocation, but degrades sharply near full and needs tombstones

Probe Count Demo

Linear probing can need several steps when slots cluster. Here we count probes to find a free slot.

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

Quick Check

Test your collision-handling knowledge.

Recap

You explored how hash tables resolve collisions.

Chaining stores a linked list per bucket
Open addressing probes for a free slot
Probing variants: linear, quadratic, double hashing
Open addressing needs tombstones for deletion

Frequently asked questions

Is the “Collision Handling” lesson free?

Yes — the full text of “Collision Handling” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.

What will I learn in “Collision Handling”?

Chaining and probing. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start C Academy?

No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Collision Handling” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this C Academy lesson?

Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to C Academy