Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

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.

  1. A hash function converts the key into a number.
  2. That number is reduced to a valid array index, typically with the remainder operator.
  3. The pair is stored at that index, in a slot often called a bucket.
key "apple"  → hash function → 8243 → 8243 % 8 = 3 → bucket 3

To 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 buckets

Six 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 = 11

In 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))); // false

Three things are going on:

  • A Map keeps the number 1 and 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 n items, so it costs O(n) space.
  • No sorted order. Map and Set remember 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 a Set.
  • 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 a Map.
  • 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:

  1. Contains Duplicate: the "seen" set.
  2. Two Sum: looking up the value you need.
  3. Group Anagrams: choosing a key that groups items.
  4. Longest Substring Without Repeating Characters: a map of last positions.
  5. 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 Map for key-value pairs and Set for membership.
  • The cost is extra memory, and there is no sorted order.