Hash Functions
Mapping keys to buckets.
Hash Functions is a free C Academy lesson on CoddyKit — lesson 1 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.
What Is a Hash Function
A hash function takes a key and produces an integer index into an array of buckets. It is the heart of a hash table, turning arbitrary keys like strings into fast array positions.
- Input: a key (string, integer, etc.)
- Output: a bucket index in
[0, capacity)
Properties of a Good Hash
A good hash function is deterministic, fast, and spreads keys uniformly across buckets.
- Same key always gives the same index
- Small key changes cause large index changes (avalanche)
- Few collisions for typical data
Mapping to a Bucket
Once you compute a raw hash value, you map it into the table using the modulo operator: index = hash % capacity.
Use an unsigned type so the modulo never produces a negative index.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16;
unsigned index = (unsigned)(hash % capacity);
printf("bucket = %u\n", index);
return 0;
}A Simple Sum Hash
The simplest string hash adds up character values. It is easy but distributes poorly because anagrams collide.
Run it to see two different strings hashing to nearby values.
#include <stdio.h>
unsigned long sum_hash(const char *s) {
unsigned long h = 0;
while (*s) h += (unsigned char)*s++;
return h;
}
int main(void) {
printf("%lu\n", sum_hash("abc"));
printf("%lu\n", sum_hash("cba"));
return 0;
}The DJB2 Hash
DJB2 is a classic, well-distributed string hash by Daniel J. Bernstein. It starts at 5381 and uses hash * 33 + c.
The multiply-and-add mixes bits far better than a plain sum.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++))
h = ((h << 5) + h) + c; /* h * 33 + c */
return h;
}
int main(void) {
printf("%lu\n", djb2("hello"));
printf("%lu\n", djb2("world"));
return 0;
}The FNV-1a Hash
FNV-1a XORs each byte then multiplies by a prime. It is simple, fast, and widely used.
Order: XOR first, then multiply (that is the 1a variant).
#include <stdio.h>
unsigned long fnv1a(const char *s) {
unsigned long h = 1469598103934665603UL;
while (*s) {
h ^= (unsigned char)*s++;
h *= 1099511628211UL;
}
return h;
}
int main(void) {
printf("%lu\n", fnv1a("key1"));
printf("%lu\n", fnv1a("key2"));
return 0;
}Hashing Integers
Integer keys still need mixing, because x % capacity alone clusters when keys share patterns. A multiplicative mix (Knuth) spreads bits.
#include <stdio.h>
unsigned hash_int(unsigned x, unsigned cap) {
x *= 2654435761u; /* Knuth multiplicative */
return x % cap;
}
int main(void) {
for (unsigned i = 0; i < 5; i++)
printf("%u -> %u\n", i, hash_int(i, 8));
return 0;
}Power-of-Two Capacities
When the capacity is a power of two, you can replace % capacity with a fast bitwise AND: hash & (capacity - 1).
This works only because the low bits of a power-of-two minus one form a full mask.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16; /* power of two */
unsigned index = (unsigned)(hash & (capacity - 1));
printf("bucket = %u\n", index);
return 0;
}Why Modulo Can Be Slow
The % operator compiles to a division instruction, which is slower than AND. In tight loops this matters.
- Power-of-two table: use AND mask
- Prime-sized table: use modulo (better distribution for weak hashes)
Collisions Are Inevitable
By the pigeonhole principle, mapping many keys into fewer buckets guarantees collisions. A good hash minimizes them but cannot eliminate them.
The next lesson covers how to resolve collisions.
Distribution Demo
Let us count how DJB2 distributes a few keys across 8 buckets. Good hashes spread fairly evenly.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
return h;
}
int main(void) {
const char *keys[] = {"apple", "banana", "cherry", "date"};
int counts[8] = {0};
for (int i = 0; i < 4; i++)
counts[djb2(keys[i]) % 8]++;
for (int i = 0; i < 8; i++)
printf("bucket %d: %d\n", i, counts[i]);
return 0;
}Quick Check
Test your understanding of hash function basics.
Recap
You learned what a hash function does and how to map keys to buckets.
- Good hashes are deterministic, fast, and uniform
- DJB2 and FNV-1a are solid string hashes
- Map with
% capacity, or& (capacity-1)for powers of two - Use unsigned types; collisions are unavoidable
Frequently asked questions
Is the “Hash Functions” lesson free?
Yes — the full text of “Hash Functions” 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 “Hash Functions”?
Mapping keys to buckets. 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 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Hash Functions” 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.