JS-201 · Lesson 5 of 12 · 25 min
Hash tables
▶ Video coming soon A video version of this lesson is on the way.
Lessons 1 and 2 leaned on one promise: looking up a key in a Map or a Set takes about the same time whether it holds ten entries or ten thousand. At the fifth session, on Tuesday, September 21, Gareth asks Mira how that can possibly be true. "An array can only find something fast if you already know its index," she says. "Exactly," says Gareth. "So a Map has to turn your key into an index. That is what a hash table does."
This lesson builds a small hash table from scratch, shows what makes one fast and what makes one slow, and explains the practical rules that follow for Map and Set keys in JavaScript.
From keys to indexes
A hash table stores entries in an array of slots called buckets. To decide which bucket a key belongs in, it passes the key to a hash function, which turns the key into a whole number called its hash. The remainder after dividing the hash by the number of buckets gives a bucket index between 0 and the number of buckets minus 1. To find the key again later, the table hashes it again, which gives the same bucket, and looks only there.
A hash function must be deterministic: the same key must always give the same hash, or entries would be lost. A good hash function also spreads different keys evenly across the possible numbers, so that the buckets fill evenly. It should be fast too, because it runs on every lookup. The function below is a common, simple choice for strings: it goes through the characters, multiplying the running total by 31 and adding each character's code.
function hashString(s) {
let h = 0;
for (let i = 0; i < s.length; i++) h = (Math.imul(h, 31) + s.charCodeAt(i)) >>> 0;
return h; // a whole number from 0 to 2**32 - 1
}
for (const email of ['ana@example.org', 'ben@example.org', 'chi@example.org', 'ana@example.org']) {
const h = hashString(email);
console.log(email.padEnd(16), String(h).padStart(10), '-> bucket', h % 8);
}ana@example.org 4053768180 -> bucket 4 ben@example.org 2002141227 -> bucket 3 chi@example.org 3460032196 -> bucket 4 ana@example.org 4053768180 -> bucket 4
What this code does
hashString builds a number from the character codes of the string, multiplying by 31 at each step. Math.imul multiplies as 32-bit integers and the unsigned right shift by zero keeps the result a non-negative whole number, so the value never grows without limit. The same email always gives the same hash and therefore the same bucket, which is what makes lookups possible.
The multiplier 31 is traditional because it is an odd prime that mixes the bits of the characters well and is cheap to compute. It is the multiplier used by Java's String.hashCode. Real JavaScript engines use stronger, faster hash functions written in C++, but the principle is the same.
Collisions and chaining
There are far more possible keys than buckets, so sooner or later two different keys land in the same bucket. This is a collision, and every hash table must handle it. The simplest method is separate chaining: each bucket holds a small list of the entries that hashed to it. A lookup hashes the key, goes to the bucket and checks the few entries in its list one by one, comparing the actual keys. The hash narrows the search from the whole table to one short list.
The other main method, open addressing, stores every entry directly in the bucket array and, on a collision, probes the next buckets in a fixed pattern until it finds a free one. It uses memory more compactly and is popular inside engines. Both methods give the same promise as long as the table is not too full.
Building a small hash map
The class below is a complete, if simple, hash map with separate chaining. Each bucket is an array of [key, value] pairs. set looks for the key in its bucket and either replaces the value or adds a new pair. get searches the bucket. The probes counter records how many entries were compared, which is the real measure of a lookup's cost.
function hashString(s) {
let h = 0;
for (let i = 0; i < s.length; i++) h = (Math.imul(h, 31) + s.charCodeAt(i)) >>> 0;
return h; // a whole number from 0 to 2**32 - 1
}
class HashMap {
constructor(capacity = 8) { this.buckets = Array.from({ length: capacity }, () => []); this.size = 0; this.probes = 0; }
#bucket(key) { return this.buckets[hashString(key) % this.buckets.length]; }
set(key, value) {
const b = this.#bucket(key);
for (const entry of b) { this.probes++; if (entry[0] === key) { entry[1] = value; return; } }
b.push([key, value]);
this.size++;
if (this.size / this.buckets.length > 0.75) this.#resize();
}
get(key) {
for (const [k, v] of this.#bucket(key)) { this.probes++; if (k === key) return v; }
return undefined;
}
#resize() { // double the buckets and put every entry in its new place
const old = this.buckets;
this.buckets = Array.from({ length: old.length * 2 }, () => []);
for (const b of old) for (const [k, v] of b) this.#bucket(k).push([k, v]);
}
}
const shifts = new HashMap();
shifts.set('kitchen-0900', 'Ana');
shifts.set('garden-1000', 'Ben');
shifts.set('counter-1100', 'Chi');
shifts.set('kitchen-0900', 'Dev'); // same key: the value is replaced
console.log(shifts.get('kitchen-0900'), shifts.get('garden-1000'), shifts.get('grocery-0830'));
console.log('size', shifts.size, 'buckets', shifts.buckets.length);
const big = new HashMap();
for (let i = 0; i < 10000; i++) big.set('volunteer-' + i, i);
big.probes = 0;
for (let i = 0; i < 10000; i++) big.get('volunteer-' + i);
console.log('buckets', big.buckets.length, '| average probes per get:', (big.probes / 10000).toFixed(2));Dev Ben undefined size 3 buckets 8 buckets 16384 | average probes per get: 1.47
What this code does
Setting an existing key finds it in its bucket and replaces the value, so the size stays at three, and a missing key returns undefined. With 10,000 volunteers the table has grown to 16,384 buckets, and an average lookup compares fewer than two entries. That is the constant-time behaviour a Map promises, achieved by keeping the chains short.
Load factor and resizing
Chains stay short only if there are enough buckets. The load factor of a hash table is the number of entries divided by the number of buckets. With a good hash function, the average chain length equals the load factor, so a table with a load factor of 0.75 checks about one entry per successful lookup. Let the load factor climb to 10 and every lookup checks about ten entries.
So a hash table resizes. When the load factor passes a limit, often around 0.75, it creates a bucket array twice as large and moves every entry into its new bucket, because the remainder after division depends on the number of buckets. That move is O(n), but as with array push, the doubling makes it rare enough that insertion is amortized O(1). The HashMap class above does exactly this in its private resize method.
function hashString(s) {
let h = 0;
for (let i = 0; i < s.length; i++) h = (Math.imul(h, 31) + s.charCodeAt(i)) >>> 0;
return h; // a whole number from 0 to 2**32 - 1
}
function averageChain(nKeys, nBuckets) {
const counts = new Array(nBuckets).fill(0);
for (let i = 0; i < nKeys; i++) counts[hashString('volunteer-' + i) % nBuckets]++;
const used = counts.filter((c) => c > 0);
const longest = Math.max(...counts);
return { load: (nKeys / nBuckets).toFixed(2), longest, emptyBuckets: nBuckets - used.length };
}
console.log(averageChain(3000, 4096));
console.log(averageChain(3000, 1024));
console.log(averageChain(3000, 64));{ load: "0.73", longest: 4, emptyBuckets: 1960 }
{ load: "2.93", longest: 11, emptyBuckets: 268 }
{ load: "46.88", longest: 81, emptyBuckets: 0 }What this code does
averageChain puts 3,000 keys into tables of different sizes and reports the load factor, the longest chain and the number of empty buckets. With 4,096 buckets the chains are very short, while with only 64 buckets each chain holds dozens of entries and every lookup slows down. Keeping the load factor below about 1 is what keeps lookups constant time.
What makes a hash function bad
A poor hash function sends many keys to the same few buckets, and then the table is really a handful of long lists. Adding up the character codes is the classic mistake. It is deterministic and fast, but every rearrangement of the same letters gives the same total, and totals for similar strings cluster in a narrow range. The comparison below hashes 1,000 shift codes both ways.
function hashString(s) {
let h = 0;
for (let i = 0; i < s.length; i++) h = (Math.imul(h, 31) + s.charCodeAt(i)) >>> 0;
return h; // a whole number from 0 to 2**32 - 1
}
function sumHash(s) { let h = 0; for (const ch of s) h += ch.charCodeAt(0); return h; }
function spread(fn, keys, buckets) {
const counts = new Array(buckets).fill(0);
for (const k of keys) counts[fn(k) % buckets]++;
return { longestChain: Math.max(...counts), emptyBuckets: counts.filter((c) => c === 0).length };
}
const keys = [];
for (let day = 1; day <= 40; day++) for (let slot = 0; slot < 25; slot++) keys.push('D' + day + '-S' + slot);
console.log(keys.length, 'keys into 1024 buckets');
console.log('sum of codes:', spread(sumHash, keys, 1024));
console.log('times 31: ', spread(hashString, keys, 1024));
console.log(sumHash('D12-S3') === sumHash('D21-S3'), hashString('D12-S3') === hashString('D21-S3'));1000 keys into 1024 buckets
sum of codes: { longestChain: 44, emptyBuckets: 964 }
times 31: { longestChain: 4, emptyBuckets: 339 }
true falseWhat this code does
spread counts how many keys land in each bucket for each hash function. The character-sum hash squeezes 1,000 keys into a small range of totals, leaving most buckets empty and making some chains very long. Multiplying by 31 at each step makes the order of the characters matter, so D12-S3 and D21-S3 no longer collide and the keys spread out.
In the worst case, every key hashes to the same bucket, and every lookup becomes a linear search: O(n). Attackers have used this. A hash flooding attack sends a server thousands of carefully chosen keys, such as form field names, that all collide, so that one request takes the server seconds to process. Modern engines and servers defend against it with hash functions that include a secret random value chosen when the program starts, so outsiders cannot predict collisions.
How this explains Map and Set
A JavaScript Map or Set is a hash table built into the engine. It hashes each key, keeps its chains or probes short by resizing, and therefore offers O(1) average get, set, has and delete. JavaScript also requires Map and Set to remember insertion order, so engines keep the entries in a separate list in the order they were added, with the hash table pointing into it. That is why iterating a Map is fast and predictable.
The key rules from Lesson 2 follow from hashing. Numbers and strings are hashed by their value, so two equal strings always find each other. Objects are hashed by identity: the engine gives each object its own hidden hash, unrelated to its contents. That is fast and safe, because an object's contents can change after it is used as a key, but it means a new object with the same contents is a different key. When the key is really a combination of values, such as a date and an area, build a string key from them.
const signups = [
{ date: '2027-09-21', area: 'Kitchen' }, { date: '2027-09-21', area: 'Garden' },
{ date: '2027-09-21', area: 'Kitchen' }, { date: '2027-09-22', area: 'Kitchen' },
];
// Object keys: every sign-up makes a new object, so nothing is counted together.
const wrong = new Map();
for (const s of signups) {
const key = { date: s.date, area: s.area };
wrong.set(key, (wrong.get(key) ?? 0) + 1);
}
console.log('object keys:', wrong.size, 'entries');
// String keys: equal strings are equal keys.
const right = new Map();
for (const s of signups) {
const key = s.date + '|' + s.area;
right.set(key, (right.get(key) ?? 0) + 1);
}
console.log('string keys:', [...right]);object keys: 4 entries string keys: [ [ "2027-09-21|Kitchen", 2 ], [ "2027-09-21|Garden", 1 ], [ "2027-09-22|Kitchen", 1 ] ]
What this code does
The first loop creates a fresh object as the key for every sign-up, and because objects are compared by identity, no two keys are ever equal, so each sign-up gets its own entry. The second loop joins the date and area into one string with a separator that cannot appear in either part. Equal strings hash to the same bucket and compare equal, so the counts are grouped correctly.
Choose a separator that cannot occur in the parts, or two different combinations could produce the same string: the area 'A|B' on one date might collide with some other pair. JSON.stringify of an array, such as JSON.stringify([date, area]), is a safe general-purpose way to build such keys.
WeakMap: data attached to objects
A WeakMap is a Map whose keys must be objects and which holds those keys weakly: if nothing else in the program refers to a key object, the garbage collector may remove the object, and its entry disappears with it. A WeakMap cannot be iterated and has no size, because its contents can change at any time. Its use is attaching extra data to objects you do not own, such as caching a computed total for each order object, without keeping old orders alive in memory.
const totals = new WeakMap();
let computed = 0;
function orderTotal(order) {
if (totals.has(order)) return totals.get(order);
computed++;
const t = order.lines.reduce((sum, l) => sum + l.price * l.qty, 0);
totals.set(order, t);
return t;
}
const order41 = { number: 41, lines: [{ price: 550, qty: 2 }, { price: 200, qty: 1 }] };
console.log(orderTotal(order41), orderTotal(order41), orderTotal(order41));
console.log('computed', computed, 'time(s)');1300 1300 1300 computed 1 time(s)
What this code does
orderTotal stores each order's total in a WeakMap keyed by the order object, so asking again returns the stored total without recomputing it. The counter shows the total was worked out only once in three calls. Because the WeakMap holds its keys weakly, an order that the rest of the program has finished with can be collected along with its cached total.
Hashing beyond tables
Hash functions are used far beyond hash tables. A checksum such as CRC32 detects accidental changes to a file. A cryptographic hash such as SHA-256 is designed so that nobody can find two inputs with the same hash or work backwards from a hash to its input, and it underlies digital signatures and git commit ids. The browser provides SHA-256 through crypto.subtle.digest. Passwords need yet another kind, a deliberately slow password hash such as bcrypt or Argon2, which belongs on the server and is covered in the PHP courses. The hash functions in this lesson are none of these: they are built for speed and spread, not security.
| Kind | Built for | Example |
|---|---|---|
| Table hash | Speed and even spread | hashString above, or the engine's own for Map |
| Checksum | Detecting accidental corruption | CRC32 in zip files |
| Cryptographic hash | Resisting deliberate tampering | SHA-256, git commit ids |
| Password hash | Being slow to guess | bcrypt, Argon2 (server side) |
Try it yourself
Count by date and area
Complete countSignups(signups) so that it returns a Map whose keys are strings made from the date and the area joined by |, such as 2027-09-21|Kitchen, and whose values are the number of sign-ups for that pair.
The program prints the entries in the order they first appear.
function countSignups(signups) {
const counts = new Map();
for (const s of signups) {
const key = s;
counts.set(key, (counts.get(key) ?? 0) + 1);
}
return counts;
}
const signups = [
{ date: '2027-09-21', area: 'Kitchen' }, { date: '2027-09-21', area: 'Garden' },
{ date: '2027-09-21', area: 'Kitchen' }, { date: '2027-09-22', area: 'Kitchen' },
{ date: '2027-09-22', area: 'Kitchen' },
];
for (const [k, n] of countSignups(signups)) console.log(k, n);Try it yourself
Two hampers for the scale
The grocery team wants to check the scale with two hampers whose weights add up to exactly a target weight. Complete pairFor(weights, target) so that it returns the indexes [i, j] of the first pair found with i < j, or null if there is none.
Use one pass with a Map from weight to index, so the function is O(n), not two nested loops.
function pairFor(weights, target) {
for (let i = 0; i < weights.length; i++) {
for (let j = i + 1; j < weights.length; j++) {
if (weights[i] + weights[j] === target) return [i, j];
}
}
return null;
}
console.log(pairFor([8200, 9100, 7400, 10600, 5800], 16500));
console.log(pairFor([8200, 9100, 7400], 30000));
console.log(pairFor.toString().includes('new Map') ? 'one pass' : 'nested loops');Common mistakes
MistakeAdding character codes makes a good hash function.
InsteadRearranged letters collide and totals cluster. Mix in the position, for example by multiplying by 31 at each step.
MistakeA hash table lookup is always O(1).
InsteadIt is O(1) on average with a good hash and a sensible load factor; in the worst case, with every key colliding, it is O(n).
MistakeUsing a new object { date, area } as a Map key to group records.
InsteadObjects are hashed by identity. Build a string key, or use JSON.stringify of an array.
MistakeResizing a hash table makes inserts slow.
InsteadEach resize is O(n), but doubling makes resizes rare, so insertion is amortized O(1).
MistakeUsing a fast table hash for passwords.
InsteadPasswords need a slow password hash such as bcrypt or Argon2, on the server.
Summary and key terms
- A hash table stores entries in an array of buckets and uses a hash function to turn each key into a bucket index, using the remainder after dividing by the number of buckets.
- A hash function must be deterministic and should spread keys evenly and run fast.
- Different keys can land in the same bucket, a collision, which separate chaining handles with a short list per bucket and open addressing handles by probing other buckets.
- The load factor, entries divided by buckets, sets the average chain length, so tables double their buckets and rehash when it passes a limit such as 0.75, giving amortized O(1) insertion.
- A bad hash such as a sum of character codes clusters keys and makes lookups slow, and deliberate collisions are the basis of hash flooding attacks.
- Map and Set are engine hash tables that also keep insertion order.
- Strings and numbers are hashed by value and objects by identity, so composite keys should be strings.
- WeakMap holds object keys weakly for caches attached to objects.
- Checksums, cryptographic hashes and password hashes are different tools for different jobs.
- hash table
- A structure that stores entries in buckets chosen by a hash of the key, giving fast average lookup.
- hash function
- A function that turns a key into a whole number in a deterministic way.
- bucket
- One slot of a hash table's array, holding the entries whose keys map to it.
- collision
- Two different keys landing in the same bucket.
- separate chaining
- Handling collisions by keeping a list of entries in each bucket.
- open addressing
- Handling collisions by placing an entry in another free bucket found by a fixed probing pattern.
- load factor
- The number of entries in a hash table divided by its number of buckets.
- rehashing
- Moving every entry to a new, larger bucket array when the table resizes.
- hash flooding
- An attack that sends many colliding keys to slow a server's hash tables down.
- WeakMap
- A map with object keys held weakly, so entries vanish when their keys are no longer used elsewhere.
Practice problems
Work each problem on paper first, then reveal the answer to check.
What two steps turn a key into a bucket index?
Show answer
Hash the key to a whole number, then take the remainder after dividing by the number of buckets.
A table has 1,000 entries and 2,048 buckets. What is its load factor?
Show answer
About 0.49.
Why must a table move its entries when it doubles its buckets?
Show answer
Bucket indexes come from the remainder after dividing by the number of buckets, which has changed.
Why are 'stop' and 'pots' a problem for a sum-of-codes hash?
Show answer
They contain the same letters, so their sums and buckets are the same.
Why can a WeakMap not report its size?
Show answer
Entries can disappear whenever their key objects are collected, so the size is not stable.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.