Hash Tables Explained: How Map and Set Find Things Instantly
How a hash table turns a key into a position, why lookups are O(1) on average, how collisions are handled, and when to use Map and Set in JavaScript.
· Updated · 10 min read
A hash table stores key–value pairs and finds the value for a key in constant time on average, however many pairs it holds. It is the structure behind Map, Set and plain objects in JavaScript, and it is the most common way to turn a slow solution into a fast one.
How a hash table finds a key
Underneath, a hash table is an array. The trick is deciding which position each key goes to.
- A hash function converts the key into a number.
- That number is reduced to a valid array index, typically with the remainder operator.
- The pair is stored at that index, in a slot often called a bucket.
key "apple" → hash function → 8243 → 8243 % 8 = 3 → bucket 3To look up "apple" later, the table repeats the same calculation, lands on bucket 3 and reads the value. There is no searching, which is why the cost does not depend on how many items are stored.
A hash function you can read
Real hash functions are carefully engineered, but the idea fits in a few lines. This one turns a piece of text into a bucket number:
function simpleHash(text, buckets) {
let hash = 0;
for (const ch of text) {
hash = (hash * 31 + ch.codePointAt(0)) % buckets;
}
return hash;
}Each character's code is mixed into a running number, and the remainder keeps the result between 0 and buckets - 1. With 8 buckets:
| Key | Bucket |
|---|---|
| kiwi | 0 |
| cherry | 1 |
| apple | 2 |
| grape | 3 |
| plum | 4 |
| banana | 5 |
A hash function must have three properties:
- Consistent. The same key always gives the same number. Otherwise a stored value could never be found again.
- Well spread. Different keys should land in different buckets as far as possible.
- Fast. It runs on every insert and every lookup.
Multiplying by 31 at each step is what makes the order of the letters matter. Simply adding the character codes would send "tea" and "eat" to the same bucket every time.
Collisions
Different keys can produce the same index. This is a collision, and every hash table needs a rule for it. The two common ones are:
- Chaining. Each bucket holds a small list of pairs. On a collision, the new pair is added to that list, and a lookup scans only that one bucket.
- Open addressing. On a collision, the table tries the next free slot according to a fixed rule, and lookups follow the same rule.
With a good hash function, pairs are spread evenly and each bucket holds very few of them.
Collisions are not rare accidents. With the function above and 8 buckets, "apple" and "mango" both land in bucket 2, and "grape" and "lemon" both land in bucket 3. Any table with more possible keys than buckets must have them.
Build a small hash table
Putting the pieces together gives a working table in about twenty lines. It uses chaining: each bucket is an array of [key, value] pairs.
class TinyHashTable {
constructor(size = 8) {
this.buckets = Array.from({ length: size }, () => []);
}
bucketFor(key) {
return this.buckets[simpleHash(key, this.buckets.length)];
}
set(key, value) {
const bucket = this.bucketFor(key);
const pair = bucket.find((entry) => entry[0] === key);
if (pair) {
pair[1] = value; // the key exists: replace its value
} else {
bucket.push([key, value]); // a new key: add it to the bucket
}
}
get(key) {
const pair = this.bucketFor(key).find((entry) => entry[0] === key);
return pair ? pair[1] : undefined;
}
}Both set and get do the same two things: work out the bucket, then look through that one bucket for the key. The search inside a bucket is a loop, but over only the handful of pairs that collided, not over the whole table.
Storing the key alongside the value is essential. The bucket number alone cannot tell "apple" from "mango"; comparing the stored key can.
A real implementation adds deletion, keys of any type, and resizing, which is the next section.
Load factor and resizing
How full a table is has a name, the load factor:
load factor = number of items ÷ number of bucketsSix items in eight buckets is a load factor of 0.75. The higher it goes, the more keys share buckets and the slower lookups become. So a table watches its load factor, and when it passes a limit, commonly somewhere around 0.75, it resizes: it creates a larger set of buckets, usually twice as many, and places every item again.
Every item has to be placed again because the bucket number depends on the number of buckets:
hash 8243: 8243 % 8 = 3 8243 % 16 = 3
hash 8251: 8251 % 8 = 3 8251 % 16 = 11In 8 buckets those two keys collide. In 16 they separate. That is how resizing thins the buckets out.
What each operation costs
| Operation | Average | Worst case |
|---|---|---|
| Insert | O(1) | O(n) |
| Look up by key | O(1) | O(n) |
| Delete by key | O(1) | O(n) |
| Find by value | O(n) | O(n) |
The worst case happens when many keys land in the same bucket. Tables avoid this by resizing: when they get too full, they allocate a larger array and place every pair again. As with a dynamic array, that single step is expensive but rare, so the average stays O(1).
Hash tables in JavaScript
| Type | Stores | Use it for |
|---|---|---|
Map |
Key–value pairs, keys of any type | Lookups, counting, grouping |
Set |
Unique values | Membership checks, removing duplicates |
| Plain object | Key–value pairs, string or symbol keys | Fixed, known property names |
For algorithm problems, prefer Map and Set. They accept any key type, report their size with .size, and keep no inherited keys that could clash with yours.
// Count how often each character appears.
function countCharacters(text) {
const counts = new Map();
for (const ch of text) {
counts.set(ch, (counts.get(ch) ?? 0) + 1);
}
return counts;
}
countCharacters("hello"); // Map { h → 1, e → 1, l → 2, o → 1 }// Remove duplicates while keeping the first occurrence of each value.
const unique = [...new Set([3, 1, 3, 2, 1])]; // [3, 1, 2]Keys: what works and what surprises
const byKey = new Map();
byKey.set(1, "the number");
byKey.set("1", "the text");
console.log(byKey.size); // 2
const plain = {};
plain[1] = "the number";
plain["1"] = "the text";
console.log(Object.keys(plain).length); // 1
const point = [1, 2];
byKey.set(point, "saved");
console.log(byKey.get(point)); // "saved"
console.log(byKey.get([1, 2])); // undefined
console.log(byKey.has(String(point))); // falseThree things are going on:
- A
Mapkeeps the number1and the text"1"apart. A plain object turns every key into text, so they become the same key and the second assignment overwrites the first. - An array or object used as a key is matched by identity: only the very same array finds the value. A new array with the same contents is a different key.
- To match by contents, make a text key yourself, for example
point.join(","), and use that for both storing and looking up.
Map or plain object
Map |
Plain object | |
|---|---|---|
| Key types | Anything | Text and symbols only |
| Number of items | .size |
Object.keys(obj).length, which is O(n) |
| Order when looping | Insertion order | Mostly insertion order, but whole-number keys come first |
| Inherited keys | None | Some, such as toString |
| Convert to JSON | Needs a conversion step | Direct |
| Best for | Lookups, counting, grouping in an algorithm | Records with fixed, known fields |
A worked example: from a nested loop to a lookup
The task: return the first value in a list that has appeared before.
The slow way checks each value against all the earlier ones: a loop inside a loop, O(n²). A Set remembers the earlier values, so each check is one lookup.
function firstRepeat(values) {
const seen = new Set();
for (const value of values) {
if (seen.has(value)) return value;
seen.add(value);
}
return null;
}For [3, 1, 4, 1, 3]:
| Value | In the set already? | Set afterwards |
|---|---|---|
| 3 | No | 3 |
| 1 | No | 3, 1 |
| 4 | No | 3, 1, 4 |
| 1 | Yes: return 1 |
One pass, with a constant-time check at each step: O(n) time, at the price of O(n) memory for the set. That trade, memory for speed, is the whole point of a hash table.
When a hash table is the right choice
Use one when the problem involves:
- "Have I seen this before?" Store seen values in a
Set. - "How many times does each thing appear?" Count in a
Map. - "Find the item that matches this one." Store items by the property you search on.
- Grouping. Use the group name as the key and a list as the value.
The general idea, replacing a search loop with a lookup, is covered in the hashing pattern.
The trade-offs
- Extra memory. A hash table can hold up to
nitems, so it costs O(n) space. - No sorted order.
MapandSetremember insertion order, but they cannot give you the smallest key or the keys in sorted order without sorting them separately. - Keys are compared by identity for objects. Two different arrays with the same contents are different keys. Convert them to a string or number if you need them to match.
- Worst-case behaviour. The O(1) is an average. A poor hash function, or keys chosen to collide, can push every item into a few buckets and make each operation O(n).
Common mistakes
- Using an array as a "seen" list.
array.includes(x)is a loop. Inside another loop it brings back the O(n²) you were trying to remove. Use aSet. - Expecting two equal-looking arrays or objects to be the same key. They are matched by identity. Build a text key.
- Using a plain object for arbitrary keys. Numbers and text collide, and keys such as
"constructor"already exist on it. Use aMap. - Changing a key after storing it. If an object used as a key is modified, nothing breaks in JavaScript, because identity is unchanged, but a text key built from its old contents no longer matches.
- Relying on sorted order. A hash table has none. Sort the keys when you need them in order.
Practise
The hashing pattern shows the three standard ways to use a hash table in a problem. Then:
- Contains Duplicate: the "seen" set.
- Two Sum: looking up the value you need.
- Group Anagrams: choosing a key that groups items.
- Longest Substring Without Repeating Characters: a map of last positions.
- Subarray Sum Equals K: counting running totals.
Summary
- A hash table is an array of buckets plus a function that turns a key into a bucket number.
- Insert, look up and delete are O(1) on average, because the position is calculated, not searched for.
- Collisions are normal. Chaining or open addressing handles them.
- When the table gets too full it resizes, which keeps the buckets short.
- In JavaScript, use
Mapfor key-value pairs andSetfor membership. - The cost is extra memory, and there is no sorted order.