Hash Maps and Sets

The Lookup Problem
The Big Idea: Turn a Key into a Position
Hash Functions
Collisions and Chaining
Load Factor and Resizing
What Each Operation Costs
Map, Set, and Plain Objects in JavaScript
Pattern: Frequency Counting
Pattern: Two Sum and "Have I Seen It?"
More Interview Problems
Recipe: The hashmap Module
Try It Yourself

1. The Lookup Problem

Here is a question you answer constantly: "given this key, find the thing that goes with it." A user ID and the user's record. A product code and its price. A word and how many times it appeared. A URL and its cached response.

With an array, finding by key means scanning from the start until you hit it: O(n). With a sorted array you can binary search in O(log n). Better, but you must keep the array sorted. What we want is a structure where the cost of looking up one key does not grow with the number of items at all.

That structure is the hash table, and it is probably the most useful data structure in everyday programming. In JavaScript it is behind Map, Set, and objects used as dictionaries. In Python it is dict and set, in Java it is HashMap, in Go it is map. Learn it once and you understand all of them.

In this chapter you learn how it works, then build one yourself, then use it to solve problems that look hard until you see the trick.

2. The Big Idea: Turn a Key into a Position

Recall from Arrays and Strings that reading arr[i] is instant, because the position is computed with arithmetic. A hash table borrows that trick. It keeps an ordinary array (the buckets) and uses a function to turn any key into an index:

key "cat"  --hash-->  193488125  --mod 8-->  5   -> go to bucket 5

Storing is "compute the index, put the value in that bucket". Finding is "compute the same index, look in that bucket". You never scan. The only work is computing the index, which depends on the length of the key, not on how many items are stored.

Two small ideas make this work:

A hash function that turns a key (a string, say) into a big non-negative integer. The same key must always give the same integer.
The modulo operator to shrink that big number into a valid bucket index: hash % bucketCount. (If you want a refresher on %, see Modular Arithmetic.)

3. Hash Functions

A good hash function has three properties:

Deterministic: the same key always gives the same number.
Fast: it must be cheap, since it runs on every operation.
Well spread: different keys should land in different places. Keys that are similar ("user1", "user2") should still scatter.

Here is a simple, classic string hash called djb2. It starts with a magic number and, for each character, multiplies by 33 and adds the character code:

function hashString(key: string): number {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 33 + key.charCodeAt(i)) >>> 0;
  }
  return hash;
}

console.log(hashString("a"));   // 177670
console.log(hashString("ab"));  // 5863208
console.log(hashString("cat")); // 193488125
console.log(hashString("tac")); // 193506621

Check the first one by hand: 5381 * 33 + 97 (the character code of a) is 177573 + 97 = 177670. The >>> 0 at the end of each step keeps the number as a 32-bit non-negative integer so it never grows without bound or turns negative. (If >>> is new, see Bitwise Operations and Flags.)

Notice that "cat" and "tac" have the same letters but different hashes. The hash depends on the order, which is exactly what we want.

Computing a hash walks the key once, so it costs O(k) where k is the key's length. For short keys we treat that as constant, which is why we say lookups are O(1). Real engines use stronger, faster hash functions than djb2, but the job is the same.

Two practical points:

Hashing needs an immutable key. If a key could change after you stored it, its hash would change and you would never find it again. That is why Map keys are usually strings or numbers, and why using a mutable object as a key needs care.
Never use a hash for passwords or security just because it is called a hash. Table hashes optimize speed. Password hashing (bcrypt, argon2) is designed to be slow and is a different topic.

4. Collisions and Chaining

Pigeonhole problem: there are infinitely many possible keys but only a few buckets. Two different keys will sometimes land in the same bucket. This is called a collision, and every hash table has a plan for it.

Let us see one. With 8 buckets, our hash puts these four keys here:

key     hash % 8
"cat"      5
"dog"      7
"bird"     6
"fish"     7      <- collides with "dog"

The most common plan is chaining: each bucket holds a small list of all the entries that landed there.

bucket 0:  (empty)
bucket 1:  (empty)
bucket 2:  (empty)
bucket 3:  (empty)
bucket 4:  (empty)
bucket 5:  [ cat ]
bucket 6:  [ bird ]
bucket 7:  [ dog ] -> [ fish ]

To find "fish": hash it, go to bucket 7, and walk the short chain comparing keys until one equals "fish". To insert, hash it, walk the chain to check for an existing copy of the key, and add to the chain if it is not there. To delete, find it in the chain and remove it.

As long as chains stay short (one or two entries), all of this is effectively constant time. The way to keep them short is to keep enough buckets, which is the next section.

(The other family of strategies is open addressing: if the bucket is taken, try the next one, and the next. Many real engines use it. Chaining is simpler to understand, so we build that.)

5. Load Factor and Resizing

If you put a million entries into 8 buckets, every chain has about 125,000 entries and the table degrades into a slow list. The key number is the load factor: entries / buckets. A load factor near or below 1 means chains average about one entry.

So the table watches its own load factor. When it passes a limit (we use 0.75), the table resizes: it makes a new bucket array twice as big and rehashes every entry into it. (Rehashing is needed because hash % bucketCount changes when the bucket count changes.)

Resizing is O(n), but it happens rarely, and each resize doubles the capacity. The same amortized argument as for array push applies: the cost averaged over many inserts is still O(1).

Watch it happen. With a starting size of 8 buckets and a limit of 0.75, inserting 100 keys triggers resizes at 7, 13, 25, 49, and 97 entries, and the table ends with 256 buckets and a longest chain of 2. We will see this in the code in a moment.

6. What Each Operation Costs

Operation	Average	Worst case	Notes
`set(key, value)`	`O(1)`	`O(n)`	worst: every key in one bucket, or a resize
`get(key)`	`O(1)`	`O(n)`	worst: one very long chain
`has(key)`	`O(1)`	`O(n)`	same as `get`
`delete(key)`	`O(1)`	`O(n)`	same as `get`
Go through all entries	`O(n + buckets)`	same	visits every bucket
Memory	`O(n)`		the buckets and the entries

The worst case happens when many keys collide. A good hash function and resizing make that very unlikely, so people simply say hash tables are O(1). Remember what the fine print means: on average, with a decent hash function.

What a hash table does not give you:

No sorting. You cannot ask for "the smallest key" without scanning. (If you need that, a tree in Chapter 9 or a sorted array is better.)
No range queries. "All keys between a and f" needs a scan.
Memory overhead. The buckets cost more space than a packed array.

7. Map, Set, and Plain Objects in JavaScript

JavaScript gives you three hash-table-like tools. Knowing which to pick avoids many bugs.

Map

A Map stores key-value pairs. Keys can be any type, and entries come back in insertion order.

const prices = new Map<string, number>();
prices.set("apple", 1.2);
prices.set("banana", 0.5);

console.log(prices.get("apple"));    // 1.2
console.log(prices.get("grape"));    // undefined
console.log(prices.has("banana"));   // true
console.log(prices.size);            // 2
prices.delete("banana");
console.log([...prices.keys()]);     // [ 'apple' ]

Keys keep their type: the number 1 and the string "1" are different keys.

const m = new Map<number | string, string>();
m.set(1, "num");
m.set("1", "str");
console.log(m.size);   // 2
console.log(m.get(1)); // num

A Map also handles NaN as a key (it treats NaN as equal to itself), and objects as keys by identity, not by content:

console.log(new Map([[NaN, "nan"]]).get(NaN));        // nan
console.log(new Map([[{ a: 1 }, 1]]).get({ a: 1 })); // undefined (a different object)

Set

A Set stores unique values with no duplicates, using the same hash idea but with no attached value:

const tags = new Set(["js", "ts", "js", "node", "ts"]);
console.log(tags.size);      // 3
console.log(tags.has("ts")); // true
console.log([...tags]);      // [ 'js', 'ts', 'node' ]

A very common one-liner removes duplicates from an array: [...new Set(array)]. It is O(n).

Plain objects

Objects also work as dictionaries, and they are fine for small, fixed shapes such as { name: "Dara", age: 30 }. As a general dictionary they have gotchas:

Keys become strings. obj[1] and obj["1"] are the same slot.
Inherited names leak in. {}["constructor"] is not undefined: it is the built-in Object function. A "word counter" that looks up the word "constructor" can be confused by this.
Order is unusual. Integer-like keys come first, in ascending order, then other keys in insertion order.
No size property, and key order and iteration APIs are more awkward.

const o: Record<string, string> = {};
o[1] = "num";
o["1"] = "str";
console.log(Object.keys(o).length); // 1
console.log(o[1]);                  // str (it overwrote)

const dict: Record<string, number> = {};
console.log(typeof dict["constructor"]); // function (not undefined!)

console.log(Object.keys({ b: 1, 2: 1, 1: 1, a: 1 })); // [ '1', '2', 'b', 'a' ]

Rule of thumb: for an arbitrary lookup table, use Map. For a "record with known fields", use an object. For a collection of unique values, use Set.

One more Map fact: its insertion order is stable, and deleting and re-adding a key moves it to the end. That makes Map useful for simple caches (for example the "least recently used" trick: delete a key and set it again to mark it as recently used).

8. Pattern: Frequency Counting

The single most common hash map pattern: count how many times each thing appears.

function countFrequencies(items: string[]): Map<string, number> {
  const counts = new Map<string, number>();
  for (const item of items) counts.set(item, (counts.get(item) ?? 0) + 1);
  return counts;
}

const words = "the cat and the hat and the bat".split(" ");
const counts = countFrequencies(words);
console.log(counts);
// Map(5) { 'the' => 3, 'cat' => 1, 'and' => 2, 'hat' => 1, 'bat' => 1 }

The ?? 0 supplies a starting count of zero the first time we see an item. It is a single O(n) pass. Finding the most frequent word is one more pass over the map entries.

Where you meet it at work: word clouds and search indexing, "top pages" analytics, vote counting, detecting a repeated request (rate limiting), and checking whether two files have the same set of lines.

First unique character

Find the index of the first character that appears only once. Count everything, then scan again in the original order:

function firstUniqueChar(text: string): number {
  const counts = countFrequencies([...text]);
  for (let i = 0; i < text.length; i++) {
    if (counts.get(text[i]) === 1) return i;
  }
  return -1;
}

console.log(firstUniqueChar("leetcode")); // 0  ("l")
console.log(firstUniqueChar("aabb"));     // -1

Are two strings anagrams?

Two words are anagrams if they use the same letters the same number of times ("listen" and "silent"). Count the first, subtract with the second:

function isAnagram(a: string, b: string): boolean {
  if (a.length !== b.length) return false;
  const counts = countFrequencies([...a]);
  for (const ch of b) {
    const c = counts.get(ch);
    if (!c) return false; // missing, or already used up
    counts.set(ch, c - 1);
  }
  return true;
}

console.log(isAnagram("listen", "silent")); // true
console.log(isAnagram("rat", "car"));       // false

It runs in O(n). The alternative, sorting both strings and comparing, costs O(n log n). The counting version is faster, though the sorted version is shorter to write.

9. Pattern: Two Sum and "Have I Seen It?"

This is the most famous interview question there is. Given an array of numbers and a target, return the indexes of two numbers that add up to the target. Exactly one answer exists. For [2, 7, 11, 15] and target 9, the answer is [0, 1].

Brute force: try every pair. Two nested loops, O(n^2). Fine for 100 numbers, painful for 100,000.

The insight: for each number x, the partner we need is target - x. Instead of searching the array for the partner (an O(n) scan), ask a hash map "have I already seen the partner?" That answer is O(1). Remember each number and its index as you go:

function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]
console.log(twoSum([3, 2, 4], 6));      // [ 1, 2 ]
console.log(twoSum([3, 3], 6));         // [ 0, 1 ]

Trace [2, 7, 11, 15] with target 9. At 2 (index 0) we need 7; the map is empty, so store 2 -> 0. At 7 (index 1) we need 2; the map has it at index 0, so return [0, 1].

Note the order inside the loop: look up first, store second. That prevents pairing an item with itself, and it handles the [3, 3] case correctly: the second 3 finds the first one.

The cost is O(n) time and O(n) extra space. This is the usual trade from Chapter 1: we spend memory to remove an inner loop. Compare it with the sorted two-pointer version from the previous chapter, which is O(n) time and O(1) space but needs sorted input and returns positions in the sorted order. Which is better depends on what you are given.

The shape "remember what I have seen, ask if the needed partner is in it" solves a whole family of problems: duplicates, pairs with a given difference, subarrays with a given sum, and matching up transactions.

10. More Interview Problems

Group anagrams

Group a list of words so that anagrams are together. For ["eat", "tea", "tan", "ate", "nat", "bat"] the groups are [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

The insight: all anagrams become the same string when you sort their letters, so sorted letters make a perfect key for the group:

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = [...w].sort().join("");
    const group = groups.get(key);
    if (group) group.push(w);
    else groups.set(key, [w]);
  }
  return [...groups.values()];
}

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]

The cost is O(n * k log k) for n words of length k (sorting each word's letters). "Group by a computed key" is one of the most common uses of a Map in real programs, whether grouping orders by customer or log lines by request ID.

Longest consecutive sequence

Given unsorted numbers, find the length of the longest run of consecutive integers, such as 100, 4, 200, 1, 3, 2 which contains 1, 2, 3, 4 (length 4). Sorting would be O(n log n). A Set does it in O(n):

function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue; // not the start of a run
    let len = 1;
    while (set.has(n + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // 4

Only numbers that start a run (no n - 1 in the set) begin counting. That guard means each number is touched at most twice, so the total work is O(n) even though there is a while inside a for. This is an example of why you must reason about how the inner loop behaves overall, not just count nested loops.

11. Recipe: The hashmap Module

Now build your own. Create src/hash-map.ts:

// src/hash-map.ts

export function hashString(key: string): number {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 33 + key.charCodeAt(i)) >>> 0;
  }
  return hash;
}

type Entry<V> = { key: string; value: V };

// A hash map from string keys to values, using chaining.
export class HashMap<V> {
  private buckets: Entry<V>[][];
  private count = 0;

  constructor(private capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => []);
  }

  get size(): number {
    return this.count;
  }

  get bucketCount(): number {
    return this.capacity;
  }

  private indexFor(key: string): number {
    return hashString(key) % this.capacity;
  }

  set(key: string, value: V): void {
    const bucket = this.buckets[this.indexFor(key)];
    for (const entry of bucket) {
      if (entry.key === key) {
        entry.value = value; // update an existing key
        return;
      }
    }
    bucket.push({ key, value });
    this.count++;
    if (this.count / this.capacity > 0.75) this.resize(this.capacity * 2);
  }

  get(key: string): V | undefined {
    const bucket = this.buckets[this.indexFor(key)];
    for (const entry of bucket) {
      if (entry.key === key) return entry.value;
    }
    return undefined;
  }

  has(key: string): boolean {
    return this.buckets[this.indexFor(key)].some((e) => e.key === key);
  }

  delete(key: string): boolean {
    const bucket = this.buckets[this.indexFor(key)];
    const i = bucket.findIndex((e) => e.key === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.count--;
    return true;
  }

  *entries(): IterableIterator<[string, V]> {
    for (const bucket of this.buckets) {
      for (const entry of bucket) yield [entry.key, entry.value];
    }
  }

  keys(): string[] {
    return [...this.entries()].map(([k]) => k);
  }

  // Length of the longest chain: a measure of how well keys are spread.
  longestChain(): number {
    return this.buckets.reduce((max, b) => Math.max(max, b.length), 0);
  }

  private resize(newCapacity: number): void {
    const old = this.buckets;
    this.capacity = newCapacity;
    this.buckets = Array.from({ length: newCapacity }, () => []);
    for (const bucket of old) {
      for (const entry of bucket) {
        this.buckets[this.indexFor(entry.key)].push(entry);
      }
    }
  }
}

Read it slowly. set, get, has, and delete all start with indexFor(key) to pick one bucket and then only touch that bucket. The resize method makes a new bucket array and re-inserts every entry, because the index of each key depends on the capacity. The *entries method is a generator (the * and yield), a convenient way to hand back items one at a time.

Keep this file going by adding the helper functions from this chapter to the bottom of the same file. They use the built-in Map and Set:

export function countFrequencies(items: string[]): Map<string, number> {
  const counts = new Map<string, number>();
  for (const item of items) counts.set(item, (counts.get(item) ?? 0) + 1);
  return counts;
}

export function firstUniqueChar(text: string): number {
  const counts = countFrequencies([...text]);
  for (let i = 0; i < text.length; i++) {
    if (counts.get(text[i]) === 1) return i;
  }
  return -1;
}

export function isAnagram(a: string, b: string): boolean {
  if (a.length !== b.length) return false;
  const counts = countFrequencies([...a]);
  for (const ch of b) {
    const c = counts.get(ch);
    if (!c) return false;
    counts.set(ch, c - 1);
  }
  return true;
}

export function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = [...w].sort().join("");
    const group = groups.get(key);
    if (group) group.push(w);
    else groups.set(key, [w]);
  }
  return [...groups.values()];
}

export function twoSum(
  nums: number[],
  target: number
): [number, number] | null {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return null;
}

export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue;
    let len = 1;
    while (set.has(n + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

Now the tests, in src/hash-map.test.ts:

// src/hash-map.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import {
  HashMap,
  twoSum,
  isAnagram,
  groupAnagrams,
  firstUniqueChar,
  longestConsecutive,
  countFrequencies,
} from "./hash-map.ts";

test("HashMap set, get, update, delete", () => {
  const m = new HashMap<number>();
  m.set("a", 1);
  m.set("b", 2);
  m.set("a", 10);
  assert.equal(m.get("a"), 10);
  assert.equal(m.size, 2);
  assert.equal(m.delete("b"), true);
  assert.equal(m.delete("b"), false);
  assert.equal(m.has("b"), false);
  assert.equal(m.get("missing"), undefined);
});

test("HashMap survives resizing", () => {
  const m = new HashMap<number>(2);
  for (let i = 0; i < 500; i++) m.set(`key${i}`, i);
  assert.equal(m.size, 500);
  assert.ok(m.bucketCount > 2);
  for (let i = 0; i < 500; i++) assert.equal(m.get(`key${i}`), i);
});

test("twoSum", () => {
  assert.deepEqual(twoSum([2, 7, 11, 15], 9), [0, 1]);
  assert.deepEqual(twoSum([3, 3], 6), [0, 1]);
  assert.equal(twoSum([1, 2], 99), null);
});

test("anagrams, counting, and runs", () => {
  assert.equal(isAnagram("listen", "silent"), true);
  assert.equal(isAnagram("rat", "car"), false);
  assert.deepEqual(
    groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]),
    [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
  );
  assert.equal(firstUniqueChar("leetcode"), 0);
  assert.equal(countFrequencies(["a", "a"]).get("a"), 2);
  assert.equal(longestConsecutive([100, 4, 200, 1, 3, 2]), 4);
});

Run npm test. With the earlier chapters you should now see 10 tests passing and # fail 0.

Add a short demo in a new file demo3.ts to watch collisions and resizing:

import { HashMap } from "./src/hash-map.ts";

const small = new HashMap<string>();
small.set("cat", "c");
small.set("dog", "d");
small.set("bird", "b");
small.set("fish", "f");
console.log(small.size, small.bucketCount, small.longestChain());
// 4 8 2   (dog and fish share a bucket, so the longest chain is 2)
console.log(small.keys());
// [ 'cat', 'bird', 'dog', 'fish' ]   (bucket order, not insertion order)

const big = new HashMap<number>();
for (let i = 0; i < 100; i++) big.set("user" + i, i);
console.log(big.size, big.bucketCount, big.longestChain());
// 100 256 2
console.log(big.get("user42"), big.get("nobody")); // 42 undefined

Notice that keys() does not come back in insertion order: our table walks the buckets in index order, so cat (bucket 5), bird (6), dog and fish (7) appear in that order. The built-in Map goes further and remembers insertion order; ours is simpler on purpose.

12. Try It Yourself

Predict the buckets. With 8 buckets and hashString, which bucket does "cat" go to? (Use the value from section 3.) Then check with hashString("cat") % 8 in a scratch file.
Count the words. Write topWord(text) that returns the most frequent word in a sentence (lowercased). Use countFrequencies and handle the empty string by returning undefined.
Contains duplicate. Write containsDuplicate(nums) using a Set. Then write containsNearbyDuplicate(nums, k): true if two equal values sit at most k positions apart. Hint: remember the last index of each value.
Intersection of two arrays. Return the values that appear in both arrays, without duplicates. Build a Set from one array, then scan the other. State the cost, and compare it with two nested loops.
Interview-style: valid anagram with Unicode. The isAnagram above treats a string as a sequence of UTF-16 code points through the spread. What happens with "é" typed as one character versus "e" plus a combining accent? Explain the difference, and how String.prototype.normalize("NFC") helps.
Interview-style: subarray sum equals k. Count the contiguous subarrays that sum to k. Keep a running prefix sum and a Map of how many times each earlier prefix sum has occurred. For each new prefix p, add map.get(p - k) ?? 0 to the answer. Check it on [1, 2, 3] with k = 3 (answer 2), and on [1, 1, 1] with k = 2 (answer 2).
Extend the HashMap. Add a clear() method, and add getOrDefault( key, fallback). Then change resize so it also shrinks the table when the load factor falls below 0.2. Write a test that adds 1,000 keys, deletes them all, and checks that bucketCount went back down.

A hash map answers "what goes with this key?" in one step, but it knows nothing about order. The next structure is all about order and cheap insertion: the linked list. In Linked Lists you build one from scratch, see where it beats an array, and learn the pointer tricks (reversal, cycle detection, merging) that interviewers love.