Inside the Hash Function
How keys are converted into numeric values, how those values are squeezed into a fixed array range with modulo arithmetic, and why collisions are an expected consequence.
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 9 scenes and explore, respond, and learn as you go.
How does a hash function turn a key into a slot index?
A dictionary can look up a word in roughly one step, even with a million entries — and that speed comes from a single arithmetic trick.
We expect a search to scan through keys, but hash tables skip that scan entirely, so something must be turning a key straight into a slot number.
Compare key strings, their numeric codes, and the modular slot index that points to a fixed-size array, with a small hands-on hash table to test collisions.
A hash function is a deterministic map from a key to a small integer — usually by folding its bytes into a number and reducing it with modulo — so every key lands in a predictable slot.
A hash function must sort or compare keys somehow to find the right slot, the same way a binary search would.
- Cryptographic hash security
- Resolving collisions via chaining or open addressing
- Universal hashing theory
- Performance benchmarks across real workloads
- 01From key to slot in one step?slideQuestion
Pose the driving question: how can a dictionary jump straight from a word to its array slot, and what arithmetic is actually being performed on the key?
- A hash table claim: lookup in roughly O(1) time
- The mystery: keys are strings or objects, not integers
- Some function must compress keys into slot numbers
- 02Predict the mappinginteractivePrediction
Learner enters a few short keys, guesses the slot index each would land in for a table of size 7, and commits to a rule before the math is shown.
- Choose keys like 'cat', 'dog', 'ant'
- Predict each slot index in a size-7 table
- Articulate the rule you are assuming
- 03Characters have codesslideEvidence
Show that every character maps to a small integer (e.g., ASCII 'a'=97, 'b'=98), so any string can be treated as a sequence of numbers.
- Letters are already numbers under the hood
- A string is a list of integers
- That list is the raw material for hashing
- 04Fold the bytes into one numberinteractiveEvidence
A live calculator where the learner enters a key, picks a folding scheme (sum of codes vs. base-101 fold), and watches the intermediate integer appear.
- Sum-of-codes version: 97+99+116 = 312 for 'cat'
- Base-fold version multiplies by a prime at each step
- Both collapse a string into a single integer
- 05Modulo squeezes the number into a slotslideEvidence
Show that taking the folded value modulo the table size (e.g., 312 mod 7 = 4) yields an index that is always in [0, size − 1], no matter how large the intermediate number is.
- Modulo N gives a result from 0 to N−1
- This is the actual slot index
- A larger table would just change N
- 06The three-step recipeslideExplanation
Put the pieces together: encode the key as numbers, fold them into one integer, reduce it modulo the array size. This is the full hash function.
- Step 1: convert each character to its code
- Step 2: combine into a single integer
- Step 3: take the result mod table_size
- 07When two keys land on the same slotslideBoundary
Demonstrate that 'cat' and 'act' can fold to the same integer, producing the same slot — a collision is a mathematical inevitability, not a bug.
- Pigeonhole: more keys than slots means some must collide
- Anagrams are an obvious collision family
- Collisions are handled separately, not by the hash itself
- 08Hash a new key yourselfinteractiveTransfer
Learner hashes a fresh key with a table size of their choice, step by step, and checks the slot index. Then they change the table size and predict how every slot index shifts.
- Apply the three-step recipe unaided
- Change table size and recompute
- Notice that the same key can land in a different slot
- 09Answering the driving questionslideResolution
State the answer directly: a hash function encodes the key as numbers, folds them into one integer, and takes the remainder modulo the table size to produce a slot index.
- Keys become integers through character codes
- Folding combines those integers into one
- Modulo maps that integer into a valid slot
- Collisions are expected, not errors
Discussion threads for a Stage aren't available yet.
This path ends here.
