Hash Maps and Sets, From First Principles

The decision underneath the syntax

A hash-based structure trades memory for fast membership and lookup. In an interview, the important step is not remembering Map syntax. It is recognizing that the problem asks you to remember something about values you have already processed.

The core analogy: an indexed mailroom

Imagine a large mailroom with numbered cubbies. Searching every envelope whenever a resident arrives would be slow. Instead, the receptionist applies a consistent rule to the resident’s name and gets a cubby number. “Ada” always leads to the same starting cubby, so the receptionist goes directly there.

A hash table follows the same plan:

1. A key identifies what you want, such as "Ada".
2. A hash function deterministically turns the key into a number.
3. That number selects a bucket, a location in an underlying array.
4. The bucket stores the key and its associated value.

The hash is not the stored value and usually is not a unique ID. Its job is to spread keys across available buckets well enough that each lookup examines very little data.

A five-bucket example

Suppose a tiny teaching table has five buckets numbered 0 through 4. Our simplified hash function adds a word’s character codes and takes the remainder after division by five:

bucket(key) = sum(character codes) mod 5

This is useful for explanation, not a production-quality string hash. It gives:

"ant" → (97 + 110 + 116) mod 5 = 323 mod 5 = 3
"cat" → (99 +  97 + 116) mod 5 = 312 mod 5 = 2
"tac" → (116 + 97 +  99) mod 5 = 312 mod 5 = 2

The resulting table begins like this:

bucket 0  empty
bucket 1  empty
bucket 2  cat, tac
bucket 3  ant
bucket 4  empty

cat and tac are different keys but land in bucket 2. That is a collision. A collision is normal and unavoidable: a practical program can have far more possible keys than the table has buckets. Correct hash tables resolve collisions; they do not assume hashes are unique.

Collision strategy 1: separate chaining

With chaining, each bucket holds a small collection of entries. Looking up tac hashes to bucket 2, then compares keys inside that bucket until the exact key is found. The full key comparison is what distinguishes tac from cat.

Think of two residents assigned the same mailroom cubby: the cubby contains a short, labeled tray rather than discarding one resident’s mail.

Collision strategy 2: open addressing

With open addressing, every entry stays directly in the bucket array. If bucket 2 is occupied, insertion follows a defined probe sequence—perhaps bucket 3, then 4, then 0—until it finds an available position. Lookup must follow the same sequence or it may stop before reaching the key.

Deletion is more subtle in an open-addressed table. Clearing a bucket completely could make a later lookup stop too early, so implementations often leave a special deleted marker called a tombstone.

Load factor and resizing

The load factor compares stored entries with available buckets. Four entries in five buckets have load factor 4 / 5 = 0.8. As the table becomes crowded, collisions and probe lengths tend to increase.

Implementations therefore allocate a larger bucket array after a threshold and insert existing entries into the new table again. This is called resizing or rehashing. One resize can cost O(n), but it happens occasionally; spread across many insertions, the average insertion cost remains expected constant time. That averaged reasoning is called amortized analysis.

Use a Set when you only care whether a value exists. Use a Map when each key needs associated information: a count, index, group, running total, or other state.

const seen = new Set<number>()
const frequency = new Map<string, number>()

For duplicate detection, a Set is enough because the only stored fact is membership:

function hasDuplicate(values: number[]): boolean {
  const seen = new Set<number>()
  for (const value of values) {
    if (seen.has(value)) return true
    seen.add(value)
  }
  return false
}

For an earlier index, use a Map because membership alone cannot answer “where?”

Predict the output first. Then change the input so there is no duplicate and run it again.

State the invariant first

Before writing the loop, finish this sentence:

After processing the first i items, my map contains…

That sentence separates a plan from improvised syntax. For frequency counting:

After processing the first i values, counts.get(x) equals the number of times x appeared in that prefix.

function frequencies(values: string[]): Map<string, number> {
  const counts = new Map<string, number>()

  for (const value of values) {
    counts.set(value, (counts.get(value) ?? 0) + 1)
  }

  return counts
}

Operations and complexity

Typical Map and Set lookup, insertion, and deletion are expected constant time. Say expected O(1) rather than promising worst-case O(1). A single pass over n items with an O(1) expected lookup per item is expected O(n) time and usually O(n) extra space.

The word expected matters. A good hash function and reasonable load factor keep buckets small, so lookup usually does a constant amount of work. If many keys collide, a bucket may contain many entries and a lookup can approach O(n) in the worst case.

Advanced: key equality in JavaScript

String and number keys behave like value keys. Objects and arrays behave like identity keys: two separate arrays with the same contents are still different keys.

const first = [1, 2]
const second = [1, 2]
const set = new Set([first, second])
set.size // 2

When structural equality matters, convert the structure to a stable primitive key. The canonical-grouping lesson develops that idea carefully.

Common mistakes

• Checking truthiness when zero is a valid stored value; use map.has(key).
• Forgetting that object and array keys compare by identity in JavaScript.
• Counting correctly but never explaining what the count represents.
• Claiming the extra map uses constant space when it can grow with the input.

Retrieval check

Explain aloud why a Set is sufficient for detecting duplicates but insufficient for returning the earlier duplicate’s index.