HashMap vs HashSet
HashMap stores a value for each key, while HashSet stores only distinct keys, so the right choice depends on whether you need associated information or only membership.
The Data Model Difference
A HashMap stores key -> value pairs. The key is used for hashing and equality, and the value is the information attached to that key. In array interviews, common values include counts, last seen indices, first seen indices, lists of grouped words, or prefix-sum frequencies.
A HashSet stores keys only. It answers questions like whether an item has appeared before, whether a value is forbidden, or whether a candidate exists in a precomputed collection. If you never need extra information beyond presence, a set is usually the clearer and lighter abstraction.
Operations and Complexity
Both HashMap and HashSet provide expected O(1) insertion, lookup, and removal under normal hashing assumptions. For a map, the common operations are put, get, containsKey, and remove. For a set, the common operations are add, contains, and remove.
The important interview habit is to name what the structure stores. Saying use a hash table is less precise than saying use a map from value to frequency or use a set of values already seen. That precision often reveals the invariant and prevents accidental overwrites.
When to Use Each
Use a HashSet when the problem is about membership, deduplication, or seen before checks. Contains Duplicate, longest consecutive sequence membership, and visited-state tracking are classic examples. The set represents a yes-or-no fact for each key.
Use a HashMap when the problem needs a value attached to each key. Two Sum needs value to index, frequency counting needs value to count, anagram grouping needs canonical key to list of strings, and prefix-sum counting needs sum to number of previous occurrences. The map represents a relationship, not just existence.
Useful Variants
Java provides variants when ordinary hashing is not enough. LinkedHashMap maintains insertion order and can also maintain access order, which is why it is useful for LRU cache designs. It still has hash-table style expected lookup while adding a predictable iteration order.
TreeMap is different: it stores keys in sorted order and gives operations in O(log n) time. Use it when the interview problem needs ordered queries such as nearest smaller key, range iteration, or sorted traversal. Do not use TreeMap just because it sounds more powerful; the logarithmic cost is unnecessary for plain membership and counting.
Counting with HashMap and membership with HashSet
The map keeps a count per value. The set only records whether each value has appeared.
Key Takeaways
- Use HashSet for membership, deduplication, and seen-before checks.
- Use HashMap when each key needs an attached value such as a count, index, list, or cached answer.
- Both structures provide expected **O(1)** add and contains behavior with good hashing.
- LinkedHashMap adds predictable order, while TreeMap adds sorted keys at **O(log n)** cost.