HashMap vs HashSet
Use a HashSet when the only question is whether you have seen something before. Use a HashMap the moment you need to remember anything about it, including how many times you have seen it or where.
HashSet is implemented as a HashMap whose values are all the same dummy object, so the performance is identical and the choice is about what you need to store. The question to ask is what you will want when the lookup succeeds: if the answer is nothing beyond yes, a set says so in the type.
Side by side
| Dimension | HashMap | HashSet |
|---|---|---|
| Stores | Key and value per entry | Key only |
| Add | put(key, value), returns the old value | add(key), returns false if already present |
| Lookup | get or containsKey, O(1) average | contains, O(1) average |
| Duplicate key | Overwrites the value | Ignored, add returns false |
| Typical use | Frequency counts, index lookups, caches | Seen-before checks, deduplication |
| Iteration | entrySet, keySet, values | The elements themselves |
When to pick each
HashMap
- Counting: how many times each character appears, which getOrDefault turns into one line.
- Remembering a position, as in two sum, where the value you need back is the index.
- Any cache, where the key is the request and the value is the answer.
HashSet
- Duplicate detection, where add returning false is the whole algorithm.
- Visited sets in a traversal, when the nodes are not simple integers.
- Intersection and difference between two collections, which retainAll and removeAll do in place.
Using a set when you later need the thing you threw away. Finding the first repeated character with a set tells you which character repeated but not where, so the follow-up question costs a second pass. The mirror mistake is a HashMap of key to a boolean that is always true, which is a set written out longhand and reads as though the value means something.
Questions people ask
Is HashSet really a HashMap underneath?
In the JDK, yes. HashSet holds a HashMap field and stores a single shared PRESENT object as every value, so the memory per element is a map entry rather than a bare key. The practical consequence is that nothing about the performance differs, so pick on meaning rather than speed.
What happens if I use a mutable object as a key?
The entry becomes unreachable. The hash is computed when you insert, so changing a field that hashCode reads moves the object to a different bucket than the one it sits in, and both get and remove miss it while iteration still finds it. Keys must be effectively immutable, which is why String and Integer are the usual choice.
When is a plain array better than either?
When the keys are small integers or lowercase letters. A 26-slot int[] indexed by the character beats a HashMap on both speed and memory, and it is the expected answer on anagram and character-count problems. Reach for the hash structures when the key space is large or not numeric.