Hash Map vs Hash Set — When to Use Which, and Why the Distinction Matters

A hash set is a hash map that forgot to store the values. The distinction sounds trivial — one has values, the other doesn't — but picking the wrong one is a common interview tell, and picking the right one is a small credit on readability. This post is the tie-breaker: when membership is all you need, when you actually need to look something up, and how to spot which the problem is asking for.

The verdict

Hash set. Use when the only question is "have I seen this?" or "is this element in the collection?" — no associated data.

Hash map. Use when you need to retrieve or update data attached to each key — index, count, timestamp, list of neighbours, cached result.

Same underlying hash table in every language's standard library. The difference is what you retrieve on lookup: a boolean (set) or a value (map). Reach for the one whose return type matches what the problem needs, and the code reads like it means what it does.

When to reach for a hash set

• Membership check. "Has this element appeared before?" LC 217 Contains Duplicate, LC 219 Contains Duplicate II with a size constraint.
• Deduplication. Enforce uniqueness in a collection. Converting list → set → list drops duplicates in one line.
• Set arithmetic. Union, intersection, difference. LC 349 Intersection of Two Arrays.
• Presence-only visited tracking. BFS/DFS traversals where you only care whether a node was visited, not when or from where. See the BFS vs DFS post.
• "Have we been in this state before?" cycle detection in state-space search.

When to reach for a hash map

• Frequency counts. LC 383 Ransom Note, LC 49 Group Anagrams. Python's collections.Counter is a dict specialisation.
• Key → index. LC 1 Two Sum — the interviewer demands indices back, and only a map can carry them.
• Key → last-seen position. Sliding-window optimisations that jump left past the previous occurrence in O(1). See the sliding-window pattern.
• Adjacency lists. Node → list of neighbours. Graph traversals with implicit or sparse graphs.
• Memoisation. args → cached result. Python's @functools.cache is a dict under the hood.
• Grouping. key(item) → list[item]. collections.defaultdict(list) is the canonical shape.
• Enrichment. Any time the answer needs both "does the key exist?" and "what's its associated data?", the map wins.

Side by side

*Same amortised bounds either way. See the time-complexity-of-common-operations post for the per-language worst-case caveats.

Worked example — hash set (LC 217 Contains Duplicate)

Return true if any value appears at least twice; false if every element is distinct.

The only question is "has this number appeared before?" No data attached to each number matters. Hash set.

def containsDuplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

If you wrote this with a hash map — seen = {x: True for x in nums} — the values are wasted memory and the code reads as "here's a map where every value is True", which is what a set already is.

Worked example — hash map (LC 1 Two Sum)

Given an array and a target, return the indices of the two numbers that add up to target. Exactly one solution exists.

The problem demands indices back. You need to associate each value with its position. Hash map.

def twoSum(nums, target):
    seen = {}                                # value → index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

You can't write this with a hash set, because on a match you need to return the paired index, and a set has thrown that information away.

The subtle middle

Some problems could use either, but one is more idiomatic. Two litmus tests:

1. What does a lookup need to return? If a boolean answers the question, use a set. If you need to read associated data on the hit, use a map. LC 217 (set), LC 1 (map), LC 128 Longest Consecutive Sequence (set — you just check whether x - 1 exists).
2. Would zero-cost lookup values change the algorithm? If replacing "map with useless values" by "set" would leave the algorithm unchanged, you should have used a set. Interviewers notice.

Recognise the trap where a candidate uses a dict to track visits with visited[node] = True — that's a set spelled out longhand. The correct call is visited: set = set() and visited.add(node).

Bottom line

Ask: does a lookup need to return anything besides "yes I've seen it"?

• No — use a hash set.
• Yes — use a hash map, and the value type is whatever the problem asks you to retrieve.

Same underlying data structure, same complexity. Picking the right one costs nothing at runtime and reads correctly to interviewers.

For the amortised O(1) claim both structures rely on — and the language-specific worst-case caveats — see the Big-O cheat sheet and the time-complexity-of-common-operations post.