Collision Handling
Chaining and probing.
Collision Handling is a free C Academy lesson on CoddyKit. This is 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, and your progress syncs across the web and the CoddyKit app. The C Academy course includes 4 lessons in total.
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
Learn C with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 39
- Lessons
- 144
Frequently Asked Questions
Is the “Collision Handling” lesson free?
Yes — the full text of “Collision Handling” is free to read here on the web. 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. The C Academy course includes 4 lessons in total.
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, so you can start here or from the beginning and move at your own pace. This is lesson 2 of 4.
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
- Hash Functions
- Collision Handling
- Insert, Lookup, Delete
- Resizing and Load Factor