Pattern #5

Hash Map vs Hash Set

Both give fast lookup by a key. A hash map remembers information about that key; a hash set only remembers whether the key exists.

The Core Difference

Hash Map = key → value

"Bob" → 75
"Mina" → 91

Use it when each item needs extra information.

Hash Set = values only

{"Bob", "Mina"}

Use it when you only need yes or no: does it exist?

A set is not a map with missing data. Choosing a set says that membership is the only information your algorithm needs.

Hash Map: Remember Something About an Item

scores := map[string]int{
    "Alice": 90,
    "Bob":   75,
}

score := scores["Bob"] // 75

The name is the key. The score is the value. Looking up Bob answers more than “is Bob present?”—it returns Bob's stored score.

Common map values in DSA: a count, an index, a distance, a parent, or a whole list.

Hash Set: Remember Only Whether an Item Exists

visited := map[string]struct{}{
    "Alice": {},
    "Bob":   {},
}

_, seen := visited["Bob"] // seen == true

A set stores unique items. Asking about Bob returns only membership: present or absent. There is no score, count, or index attached to Bob.

Common set jobs in DSA: visited nodes, duplicate detection, and fast membership checks.

How to Choose

Do I need information ABOUT each item?

Yes → Hash Map
      word → count
      node → distance
      value → last index

Do I only need to know if the item exists?

Yes → Hash Set
      visited nodes
      seen values
      blocked IDs

How many times did this value appear?

Hash Map

The value must point to a count.

Have I visited this node?

Hash Set

Only present or absent matters.

Where did I last see this character?

Hash Map

The character must point to an index.

Is this ID blocked?

Hash Set

Only membership matters.

Go Quick Reference

Hash Map

counts := make(map[string]int)

counts["go"]++
count, exists := counts["go"]
delete(counts, "go")

Hash Set

seen := make(map[string]struct{})

seen["go"] = struct{}{}
_, exists := seen["go"]
delete(seen, "go")

Go has no built-in set type. map[T]struct{} is the usual memory-conscious set representation. A map[T]bool can be easier at first, but false and missing need careful handling.

DSA Tips That Save Time

Duplicates → Set

If an item is already in seen, you found a duplicate.

Frequency → Map

Store item → count, then increment while scanning.

Visited → Set

Mark graph or grid nodes so you do not process them again.

Position → Map

Store item → index when a future step needs its location.

Unique Window

Use a set for membership; switch to a map when duplicates need counts or last indexes.

Count Reaches Zero

Delete the key so a later existence check does not see stale state.

Interview rule: before writing a map, say what its value means—count, index, distance, parent, or group. If you cannot name a useful value, you may only need a set.

Complexity and Production Thinking

Hash Map lookup / insert / deleteO(1) averageworst: O(n)

Hash Set lookup / insert / deleteO(1) averageworst: O(n)

Space for n stored itemsO(n)worst: O(n)

In production, use a map for account ID → account record, but a set for blocked account IDs. Neither structure promises sorted iteration order, and both trade extra memory for fast average lookup.

Common Mistakes

• Using a map when no meaningful value is needed—use a set to express intent.
• Treating a missing Go map key as present because its returned value is zero—use the two-value lookup.
• Forgetting that sets remove duplicates and do not preserve insertion order.
• Assuming O(1) is guaranteed; it is average-case complexity.
• Keeping zero counts in a map when later logic uses key existence.

Remember This

HASH MAP
key → useful information
word → count
node → distance

HASH SET
item → exists or not
visited nodes
seen values

💡 Golden Rule: Need a value for every key? Use a map. Need only “have I seen it?” Use a set.

Continue to the full Hashing interview topic →