01 / The idea
You have the key. You want the thing.
Your CRM hands you a list of customers. Your own API hands you their orders. Finance wants a total per customer, and the two lists have never met. The first version everyone writes is a loop inside a loop: for each order, walk the customers until an email matches.
You have fixed this before, probably without naming it. new Map(users.map((u) => [u.id, u])), a Go map[string]Customer, a Rust HashMap. Every time you then write byId.get(order.userId), something turns that id into a place to look and goes
straight there. The JavaScript specification even requires it: a Map must use hash tables,
or something else that is faster than a scan on average.
A hash map is that something. It keeps key–value pairs in an array of buckets, uses a hash of the key to pick one bucket, and compares keys only inside it. This lesson builds a small one by hand, so that the next time a lookup misses or a map is slow, you know exactly where to look.
02 / Name the rule
Hash the key, pick a bucket, compare what is there.
A hash function turns a key into a number, and the same key always gives
the same number. Our map runs FNV-1a over the email’s bytes. With eight buckets, the last
three bits of that number choose the bucket, so ada@example.com always lands in bucket
2.
Two different keys can land in the same bucket. That is a collision, and it is normal. Our map keeps a short list in each bucket, which is called separate chaining, and compares keys one at a time inside it. The hash only narrows the search. Equality decides the answer.
The invariant: every stored key sits in the bucket its hash selects, and each key appears once. The load factor, entries divided by buckets, stays at or below 0.75. When an insert pushes it past, the map doubles its buckets and moves every key to the bucket its hash now selects.
What a hash promises, and what it does notEqual keys, equal hashes
Equal keys must give equal hashes, or a lookup would search the wrong bucket. Rust’s documentation states it as a rule for every key type. The reverse is not promised: different keys can share a hash, which is why the bucket still compares keys.
FNV-1a is here because it is short and puts every key in the same bucket in TypeScript and Go. Production maps use seeded hash functions, so nobody can choose
thousands of keys that all land in one bucket. Rust’s HashMap, for example,
uses a randomly seeded SipHash 1-3 by default.
03 / Follow one operation
Five customers, a lookup, a collision, a grow.
Five customers sit in eight buckets, one each. Look up Ada: hash, go to bucket 2, compare one key, done. Add Bjarne: his hash picks bucket 2 as well, so that bucket now holds two keys. Add Barbara: seven entries in eight buckets passes 0.75, so the map doubles and rehashes all seven. Watch what happens to Ada and Bjarne.
Each chapter is one completed call on the TypeScript example, and the highlights replay the hashes, comparisons, and moves it recorded. Try it gives you the same map and an email box, with a switch that decides whether the email is normalized first.
Hash, then look in one bucket.
8 buckets
- 0 donald
- 1 katherine
- 2 ada
- 3 dennis
- 4 ·
- 5 ·
- 6 jean
- 7 ·
5 entries ÷ 8 buckets = load 0.63
Eight buckets. Five keys.
Each email hashes to a number, and its low bits pick a bucket. No two of these five share one.
Reduced motion: choose a scene to see its completed state.
Read this scene
Each email hashes to a number, and its low bits pick a bucket. No two of these five share one.
Each email hashes to a number, and its low bits pick a bucket. No two of these five share one.
- Bucket 0: donald
- Bucket 1: katherine
- Bucket 2: ada
- Bucket 3: dennis
- Bucket 6: jean
Watch restarts when you return. Step through keeps your selected step. Try it starts a fresh map each time you open it.
04 / Read the shape
The map finds keys. The join decides what a key is.
Basic form is the map itself: buckets, a hash, key comparisons, and growth. In the wild uses it to join CRM customers to orders. Notice where each decision lives. The map compares exact strings and knows nothing about email. The join normalizes every email, keeps the first CRM record when two share an address, skips records with no email, and reports the orders it cannot match.
That split is the one to carry into your own code. The collection makes lookup fast. Deciding which two keys count as the same is your job, and it has to happen the same way when you store and when you look up.
A small separate-chaining map with string keys. FNV-1a picks a bucket, keys in that bucket are compared for equality, and the eight buckets double once the load passes 0.75. The optional trace records every hash, comparison, and move.
export type Lookup<V> = { found: true; value: V } | { found: false };
export type Entry<V> = { key: string; value: V };
export type Step = {
kind: 'hash' | 'compare' | 'found' | 'missing' | 'insert' | 'update' | 'remove' | 'grow' | 'move';
key: string;
bucket: number;
detail: number;
};
const utf8 = new TextEncoder();
// FNV-1a over the key's UTF-8 bytes: small, deterministic, and identical in all three
// languages. Production maps use seeded hashes so nobody can choose colliding keys.
export function hashKey(key: string): number {
let hash = 2166136261;
for (const byte of utf8.encode(key)) {
hash ^= byte;
hash = Math.imul(hash, 16777619) >>> 0;
}
return hash;
}
// Separate chaining: each bucket holds the entries whose hash lands there.
export class BucketMap<V> {
#buckets: Entry<V>[][] = Array.from({ length: 8 }, () => []);
#size = 0;
#comparisons = 0;
#steps: Step[] = [];
#capture: boolean;
constructor(captureTrace = false) {
this.#capture = captureTrace;
}
get size(): number {
return this.#size;
}
get bucketCount(): number {
return this.#buckets.length;
}
/** Key equality checks made so far, across every operation. */
get comparisons(): number {
return this.#comparisons;
}
#record(kind: Step['kind'], key: string, bucket: number, detail: number): void {
if (this.#capture) this.#steps.push({ kind, key, bucket, detail });
}
#locate(key: string): { bucket: number; slot: number } {
const hash = hashKey(key);
const bucket = hash & (this.#buckets.length - 1);
this.#record('hash', key, bucket, hash);
const chain = this.#buckets[bucket];
for (let slot = 0; slot < chain.length; slot++) {
this.#comparisons++;
this.#record('compare', chain[slot].key, bucket, slot);
if (chain[slot].key === key) return { bucket, slot };
}
return { bucket, slot: -1 };
}
get(key: string): Lookup<V> {
this.#steps = [];
const { bucket, slot } = this.#locate(key);
if (slot < 0) {
this.#record('missing', key, bucket, -1);
return { found: false };
}
this.#record('found', key, bucket, slot);
return { found: true, value: this.#buckets[bucket][slot].value };
}
set(key: string, value: V): 'inserted' | 'updated' {
this.#steps = [];
const { bucket, slot } = this.#locate(key);
if (slot >= 0) {
this.#buckets[bucket][slot].value = value;
this.#record('update', key, bucket, slot);
return 'updated';
}
const chain = this.#buckets[bucket];
chain.push({ key, value });
this.#record('insert', key, bucket, chain.length - 1);
this.#size++;
if (this.#size * 4 > this.#buckets.length * 3) this.#grow(); // load factor above 0.75
return 'inserted';
}
delete(key: string): Lookup<V> {
this.#steps = [];
const { bucket, slot } = this.#locate(key);
if (slot < 0) {
this.#record('missing', key, bucket, -1);
return { found: false };
}
const [entry] = this.#buckets[bucket].splice(slot, 1);
this.#record('remove', key, bucket, slot);
this.#size--;
return { found: true, value: entry.value };
}
#grow(): void {
const old = this.#buckets;
this.#buckets = Array.from({ length: old.length * 2 }, () => []);
this.#record('grow', '', old.length, this.#buckets.length);
for (let from = 0; from < old.length; from++)
for (const entry of old[from]) {
const to = hashKey(entry.key) & (this.#buckets.length - 1);
this.#buckets[to].push(entry);
this.#record('move', entry.key, from, to);
}
}
// Bucket order, not insertion order. Entries are copied; values are not deep-cloned.
buckets(): Entry<V>[][] {
return this.#buckets.map((chain) => chain.map((entry) => ({ ...entry })));
}
trace(): Step[] {
return this.#steps.map((step) => ({ ...step }));
}
}type Step struct {
Kind string `json:"kind"`
Key string `json:"key"`
Bucket int `json:"bucket"`
Detail int64 `json:"detail"`
}
type Entry[V any] struct {
Key string `json:"key"`
Value V `json:"value"`
}
// FNV-1a over the key's bytes: small, deterministic, and identical in all three
// languages. Production maps use seeded hashes so nobody can choose colliding keys.
func hashKey(key string) uint32 {
hash := uint32(2166136261)
for i := 0; i < len(key); i++ {
hash ^= uint32(key[i])
hash *= 16777619
}
return hash
}
// Separate chaining: each bucket holds the entries whose hash lands there.
type BucketMap[V any] struct {
buckets [][]Entry[V]
size int
comparisons int
steps []Step
capture bool
}
func NewBucketMap[V any](capture bool) *BucketMap[V] {
return &BucketMap[V]{buckets: make([][]Entry[V], 8), capture: capture}
}
func (m *BucketMap[V]) Len() int { return m.size }
func (m *BucketMap[V]) BucketCount() int { return len(m.buckets) }
// Comparisons counts key equality checks made so far, across every operation.
func (m *BucketMap[V]) Comparisons() int { return m.comparisons }
func (m *BucketMap[V]) record(kind, key string, bucket int, detail int64) {
if m.capture {
m.steps = append(m.steps, Step{kind, key, bucket, detail})
}
}
func (m *BucketMap[V]) locate(key string) (bucket, slot int) {
hash := hashKey(key)
bucket = int(hash & uint32(len(m.buckets)-1))
m.record("hash", key, bucket, int64(hash))
for slot, entry := range m.buckets[bucket] {
m.comparisons++
m.record("compare", entry.Key, bucket, int64(slot))
if entry.Key == key {
return bucket, slot
}
}
return bucket, -1
}
func (m *BucketMap[V]) Get(key string) (V, bool) {
m.steps = nil
bucket, slot := m.locate(key)
if slot < 0 {
m.record("missing", key, bucket, -1)
var zero V
return zero, false
}
m.record("found", key, bucket, int64(slot))
return m.buckets[bucket][slot].Value, true
}
func (m *BucketMap[V]) Set(key string, value V) string {
m.steps = nil
bucket, slot := m.locate(key)
if slot >= 0 {
m.buckets[bucket][slot].Value = value
m.record("update", key, bucket, int64(slot))
return "updated"
}
m.buckets[bucket] = append(m.buckets[bucket], Entry[V]{key, value})
m.record("insert", key, bucket, int64(len(m.buckets[bucket])-1))
m.size++
if m.size*4 > len(m.buckets)*3 { // load factor above 0.75
m.grow()
}
return "inserted"
}
func (m *BucketMap[V]) Delete(key string) (V, bool) {
m.steps = nil
var zero V
bucket, slot := m.locate(key)
if slot < 0 {
m.record("missing", key, bucket, -1)
return zero, false
}
chain := m.buckets[bucket]
value := chain[slot].Value
copy(chain[slot:], chain[slot+1:])
chain[len(chain)-1] = Entry[V]{} // release the vacated slot's references
m.buckets[bucket] = chain[:len(chain)-1]
m.record("remove", key, bucket, int64(slot))
m.size--
return value, true
}
func (m *BucketMap[V]) grow() {
old := m.buckets
m.buckets = make([][]Entry[V], len(old)*2)
m.record("grow", "", len(old), int64(len(m.buckets)))
for from, chain := range old {
for _, entry := range chain {
to := int(hashKey(entry.Key) & uint32(len(m.buckets)-1))
m.buckets[to] = append(m.buckets[to], entry)
m.record("move", entry.Key, from, int64(to))
}
}
}
// Buckets returns bucket order, not insertion order. Entries are copied.
func (m *BucketMap[V]) Buckets() [][]Entry[V] {
out := make([][]Entry[V], len(m.buckets))
for i, chain := range m.buckets {
out[i] = append([]Entry[V]{}, chain...)
}
return out
}
func (m *BucketMap[V]) Trace() []Step { return append([]Step{}, m.steps...) }Reading the TypeScriptBytes, unsigned math, and presence
Keys are strings, so the map hashes their UTF-8 bytes from TextEncoder and compares them with ===. Math.imul and >>> 0 keep the FNV-1a arithmetic in unsigned 32 bits; plain * on numbers that large
would lose precision.
Lookup<V> tells a stored undefined apart from absence. buckets() copies the entries for inspection, but a value that is an object is
still shared.
Reading the GoBytes, wrapping, and (value, ok)
Indexing a string gives bytes, so the hash loop reads key[i] directly, and uint32 multiplication wraps around exactly as FNV-1a expects.
Get and Delete return (V, bool), so a stored zero
value is never confused with a missing key. Delete shifts the rest of the bucket
left and clears the vacated slot so it cannot keep a value alive.
What would I normally use in application code?Your language already has one
The built-in one, almost always. A TypeScript Map takes any key and iterates
in insertion order. It compares keys like ===, so objects match by identity,
and 1 and "1" are different keys. A plain object also works for
string keys, but it turns every key into a string first. See the Map reference.
A Go map needs a key type that supports ==, and the specification leaves its iteration order
unspecified. A Rust HashMap needs keys that are Eq and Hash, iterates in arbitrary order,
and treats changing a key while it is inside the map as a logic error.
05 / Try a decision
The customer is there. The lookup still misses.
This is the hash map bug you will actually meet. The data is right, the map is healthy, and a lookup comes back empty anyway. Before you answer, look closely at the two strings.
06 / Follow the cost
Cheap on average, and the average is the point.
Here is every operation at a glance, with n entries and b buckets. The lookups say O(1) on average. The rest of this section is why “on average” is doing honest work.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Get or delete by key | O(1) average | O(1) | Hash once, then compare the few keys in one bucket. If every key shares a bucket, it becomes O(n). |
| Set a key | O(1) amortized | O(1) amortized | Same as a get, plus the occasional grow. A grow moves all n entries, but only when the table doubles. |
| Hash a key of k bytes | O(k) | O(k) | Every byte is read, so long keys cost more to hash and compare. TypeScript encodes the key into a k-byte buffer first; Go reads the bytes in place. |
| Join c customers to o orders | O(c + o) average | O(c) | One index over the customers, then one lookup per order. A nested loop checks up to c × o pairs. |
| Walk every entry | O(n + b) | O(n + b) | Visits every one of the b buckets, empty or not, in bucket order rather than insertion order. |
| Hold n entries | — | O(n + b) | This map never shrinks, so after many deletes b can stay far above n. |
The whole trick is the load factor. If the hash spreads keys evenly, a bucket holds about entries ÷ buckets keys, and this map keeps that at 0.75 or less. So a lookup compares about one key whether you have ten customers or ten million. That is what “O(1) average” means: a promise that rests on the keys spreading out.
When they do not spread, the promise fails. Put every key in one bucket and a lookup walks all of them, which is the O(n) worst case. A poor hash can do that by accident, and someone who knows your hash can do it on purpose. Seeded hashes exist to make the second one impractical.
A grow costs O(n) moves when it happens, and it only happens when the table doubles, so the moves spread across the inserts that filled it. That is the same argument as Dynamic array. The join is where all of this pays off: 8 key comparisons for five customers and five orders, where a nested loop checks up to 25 pairs, and the gap grows with every customer you add.
07 / Give it a real job
When the join is your job.
In a real app the two lists come from different systems. The CRM owns customers, your
service owns orders, and no database holds both. There is no JOIN to write. For the
length of this request you are the database, and the hash map is your index.
The join in In the wild builds that index once, from normalized email to row, then makes one lookup per order. Its decisions are the interesting part: which spellings of an email count as the same person, which record wins when the CRM has two, and what happens to an order nobody claims. This one keeps the first record, skips customers with no email, and reports unmatched orders instead of dropping them.
What it leaves out is real work too. RFC 5321 treats the part of an address before the @ as case-sensitive, while discouraging anyone from relying on that, so ignoring case is a policy you choose, not a fact about email. A production join would also page through both APIs, cope with a CRM that changes mid-request, and decide whether an unmatched order is a bug or a guest checkout.
Build UIs?You already build these, and some days the join is yours to write.
Where it already is in your components
users.find inside orders.map is the loop inside a loop, and it
turns up in components all the time. A Map built once, memoized on the users
in React or derived in Svelte, turns each lookup into a hash and a comparison or two.
Watch the key type: a Map compares like ===, so the id 1042 from one API
never matches the string "1042" from another.
When you have to own it
Your dashboard shows revenue per customer. Customers come from the CRM’s API, orders from yours, and nobody joined them on a server. So the component does it: normalize the email, index the customers once, look up each order, and show the orders nobody claims instead of hiding them. The index depends only on the customer list, so a new order never rebuilds it.
When the lists grow big enough that the browser feels it, the join wants to move to a server that can page, cache, and index properly. Until then, a map is exactly the right tool.
users.find inside orders.map, replaced by a Map built once. Memoized in React, derived in Svelte, and careful about the key’s type.
import { useMemo } from 'react';
type User = { id: string; name: string };
type Order = { id: string; userId: string; totalCents: number };
export function OrderList({ users, orders }: { users: User[]; orders: Order[] }) {
// The version everyone writes first: users.find inside orders.map scans the
// users for every order, users × orders checks in the worst case.
// A Map built once turns each lookup into one hash and a comparison or two.
const usersById = useMemo(() => new Map(users.map((user) => [user.id, user])), [users]);
return (
<ul>
{orders.map((order) => (
// Map compares keys like ===, so the number 1042 and the string "1042" are
// different keys. If two APIs disagree on the type, pick one before you build.
<li key={order.id}>
{usersById.get(order.userId)?.name ?? 'Unknown customer'}: {order.totalCents} cents
</li>
))}
</ul>
);
}
08 / Make the call
Reach for it when the question is “which one has this key?”
A hash map earns its place when you look things up by an exact key, again and again, and the order of entries does not matter. That covers most of the indexes you will build in application code, and your language’s built-in map already does it well.
Look elsewhere when the question changes. A handful of entries: scanning an array is simpler and fast enough. Only asking “have I seen this?”: a set says so directly. Ranges, neighbors, or sorted output: an ordered map or a sorted array. Near matches rather than exact ones: normalizing is not enough, which is what Jaro-Winkler is for. And when both lists live in one database, let the database do the join, because that is what its indexes are for.
09 / Take the idea with you
Explain the lookup without saying “hash map.”
“I turn the key into a number that tells me which small pile to check, then compare keys in that pile only. When the piles get crowded, I make more piles.” That is the whole design. The name is what you call it in a review.
Before moving on, explain three things without the name: why a collision is not a bug, why
“Ada@Example.com ” missed, and why the grow moved Bjarne but not Ada. Then go and find a find inside a loop in your own code.
Connections to follow nextRelated lessons
- Linked list keeps an order you can change in place. A map from key to list node is the LRU cache.
- Binary heap becomes an indexed heap when a map remembers where each job sits.
- Hash set is this map with the values taken away.
10 / Practice in code
Build the index your next lookup needs.
Choose a dashboard counter, a billing total, or a product catalog index. Each task uses a map to replace repeated scans with one pass to build the index and a direct lookup afterward. Switch between them in the workspace; your TypeScript and Go drafts stay with each exercise.
Hash map practice 8 min
Build a status counter
This is an experiment with ticket-style exercises, giving beginners a feel for how tasks may be described in the workplace. Leave feedback
This practice workspace is open to everyone. A free account syncs your lesson progress across devices.