In this article
Before you start
Why interviewers ask this
The wrong choice shows up as extra code, extra memory or a wrong answer. A candidate who reaches for a map when a set would do stores values nobody reads, and a candidate who reaches for a set when the problem needs a count loses the information the problem asks for. Interviewers ask "HashMap or HashSet?" because it separates people who understand the one idea behind both, hashing a key to find a slot, from people who memorised two class names.
A weak answer lists differences: "a map has values, a set does not". A strong answer says which question each structure answers, what it costs, where the constant-time promise breaks, and what changes in another language. The question appears in the first rounds of an interview loop because it is short and exposes how a candidate thinks about trade-offs.
What each one is
- HashMap
- A HashMap is the Java class that implements a hash table of key-value pairs, so that you can store, fetch and remove the value for a given key in constant time on average.
- HashSet
- A HashSet is the Java class that implements a set, a collection of distinct elements, on top of a hash table, so that you can add, remove and test membership of an element in constant time on average.
- Hash collision
- A hash collision is the situation in which two different keys are sent to the same bucket, which forces the table to compare keys to tell them apart and is the reason lookup is only constant time on average.
How HashMap works in plain words
A HashMap hashes a key to a bucket and stores a value there. Think of a coat-check desk: you hand over a coat (the value) and get a numbered ticket (the key's slot), and later the ticket takes the attendant straight to the right hook. The analogy breaks in one place: a real desk has a hook per ticket, while a HashMap squeezes many possible keys into a limited number of buckets, so two keys sometimes share a hook and the attendant must check which coat is yours.
The Java 21 documentation (read Oct 2026) says the class provides constant-time performance for get and put, "assuming the hash function disperses the elements properly among the buckets". A hash function is a rule that turns a key into a whole number. The same page says a HashMap permits the null key and null values and makes no promise about the order of its entries.
How HashSet reuses HashMap
A HashSet is a HashMap whose values are all the same placeholder. The Java 21 HashSet page (read Oct 2026) says the class implements the Set interface, "backed by a hash table (actually a HashMap instance)". Adding an element to a set stores it as a key of that inner map, paired with one shared placeholder object, and asking whether the set contains an element asks whether the map has that key.
In OpenJDK 21 HashSet.add calls map.put with one shared placeholder object for every element, so every element still occupies a full map entry and a Java HashSet saves no memory per element compared with a HashMap.3 Python's set does save memory, because it stores no value at all. So the two share one speed promise, 16 default buckets and a 0.75 default load factor. The load factor is the ratio of stored entries to buckets at which the table grows: with 16 buckets and 0.75, the 13th entry pushes the count past 12, so the table doubles to 32 buckets and rehashes.
Text description of the diagram
- A HashMap hashes a key to a bucket and stores a value there.
- A Java HashSet is backed by a HashMap and stores one shared placeholder value under every key.
Which question does each one answer?
A HashMap answers "what is stored for this key?" and a HashSet answers "have I seen this key?". Counting how many times each word appears needs a map, because each key carries a number. Removing duplicates from a list needs only a set, because presence is all that matters. Both questions are answered by hashing the key to a bucket, so neither requires sorting. Python names the same pair dict and set; its documentation calls a set "an unordered collection of distinct hashable objects" whose common uses include "membership testing, removing duplicates from a sequence" and the operations of union, intersection and difference.4
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Take the sentence "to be or not to be that is the question to be": twelve words. A set of the words has 8 distinct entries, so the set answers "how many different words?" with 8. A map from word to count answers more: "to" and "be" each appear 3 times, and every other word once.2 The set cannot tell you that, because it kept no value; the map can, at the price of storing a number per key.
That price can be measured. In Python 3.12.12, for a table of integer keys, the container itself (not the keys) takes the sizes below.2
| Keys stored | set container size | dict container size | dict / set |
|---|---|---|---|
| 10 | 728 bytes | 352 bytes | 0.48 |
| 1,000 | 32,984 bytes | 36,952 bytes | 1.12 |
| 100,000 | 4,194,520 bytes | 5,242,960 bytes | 1.25 |
| 1,000,000 | 33,554,648 bytes | 41,943,128 bytes | 1.25 |
The 10-key row runs the other way because of how each type lays out a small table: a small Python set quadruples its table once it is about 60% full (from 8 slots to 32 at the 5th key), while a dict stores dense entries plus a small index, so a tiny dict is smaller. The figures count only the container, via sys.getsizeof, not the integer keys or any values. The lesson is not "sets are always smaller"; it is that a map pays for a value slot per key, and that the gap settles near a quarter more at scale in this Python run. Java does not show that gap, because its set stores a placeholder under each key.
Now the promise itself. Constant time is an average, and the Python time-complexity table (read Oct 2026) lists membership as O(1) on average and O(n) in the worst case, with the note that the average assumes a hash function good enough to make collisions uncommon. To see the Python worst case, a class was written whose instances all hash to the same number, and 100, 200 and 400 of them were added to a set.
The count of equality checks was 5,982, then 22,355, then 93,893.2 Doubling the keys multiplied the work by about four, which is the signature of quadratic growth: each insert walks the same probe path (a CPython set uses open addressing, not chains) and compares against the keys already placed, at least n(n-1)/2 checks (4,950 for 100 keys), plus revisits of slots, which is why the run shows 5,982.
Text description of the diagram
- Adding 100 same-hash keys took 5,982 equality checks.
- Adding 400 same-hash keys took 93,893 equality checks.
Trade-offs and edge cases
Both structures share the same costs and the same risks, so the trade-off is about what you need back and which promises you rely on.
| Fact | HashMap | HashSet |
|---|---|---|
| Stores | key-value pairs | distinct elements only |
| Average add / lookup | constant time (Javadoc) | constant time (Javadoc) |
| Null | one null key, null values allowed | the null element allowed |
| Iteration order | no promise | no promise |
| Synchronized | no | no |
| Default capacity and load factor | 16 and 0.75 | 16 and 0.75 (inner HashMap) |
Thread-safety is the usual edge case. Both Javadoc pages state that the implementation "is not synchronized", so if one thread modifies a table while others read or write it, the table needs external locking, for example by wrapping it with Collections.synchronizedMap or Collections.synchronizedSet. A HashMap's iterators are also fail-fast, meaning they throw a ConcurrentModificationException, on a best-effort basis, when the map is structurally modified (an entry added or removed) during iteration by anything other than the iterator's own remove method, so replacing the value of an existing key with put does not throw and Iterator.remove() is the supported way to delete entries while looping; the Javadoc says this should only detect bugs, never be relied on for correctness.
Order is the second. Java's two classes promise no order, and the order may change over time. Python's dict is different: since version 3.7 it preserves insertion order, which the Python documentation states as a rule of the language, while a Python set records no order.4 A candidate who says "hash tables are unordered" is right for Java's HashMap and wrong for Python's dict. If you need sorted keys in Java, the right structure is a tree-based one, a different trade covered in the coding interview hub.
Keys must also behave: a key's hash must not change while it sits in the table, and equal keys must hash equally. In Python, a list cannot be a dict key or a set element because it is mutable and therefore unhashable. The same rule appears in the system design hub when a cache keys its entries.
Text description of the diagram
- Use a map when each key needs a value such as a count.
- Removing duplicates from a list needs only a set, because presence is all that matters.
How to answer it in an interview
What is the difference between a HashMap and a HashSet?
Both are hash tables, so both give constant-time average add and lookup. A HashMap stores key-value pairs and answers "what is stored for this key?". A HashSet stores only distinct keys and answers "have I seen this?"; in Java it is literally a HashMap underneath. I pick the set to deduplicate or test membership, and the map when I need a count, an index or a cached result per key. The caveat is that constant time is the average: if many keys collide, operations degrade toward linear, though Java 8 and later turn a crowded bucket into a tree, so keys that are Comparable cost O(log n) instead, and neither class is thread-safe by default.
The spoken structure is: what they share, what each stores, how you choose, then the caveat.
Common mistakes
"A HashSet is faster than a HashMap." (wrong) They use the same table and the same average cost. (right) "Same table, same lookup speed; in Java a set even stores a placeholder per key, so it saves no memory; Python's set is leaner."
"Hash tables are always O(1)." (wrong) The promise is about the average, and it needs a hash function that spreads keys. (right) "Average O(1), worst case O(n) when keys collide."
"HashMap keeps insertion order." (wrong) Java's HashMap promises no order. (right) "Use a linked or ordered variant when order matters; Python's dict does keep insertion order."
"I can use a mutable object as a key." (wrong) If a key's hash changes after insertion, the entry becomes unreachable. (right) "Keys should be immutable, or at least never change in a way that alters their hash."
Follow-up questions
Can a HashSet hold a null element?
Yes. The Java 21 documentation says the class permits the null element, and a HashMap permits one null key and any number of null values. Python has no null, but None is hashable and can be a dict key or set element.
Is a HashMap or a HashSet thread-safe?
No. Both Javadoc pages state the implementation is not synchronized, so a table that one thread modifies while others use it needs external locking or a wrapper such as Collections.synchronizedMap; ConcurrentHashMap is the usual choice when threads share a map.
What are the Python equivalents of HashMap and HashSet?
A dict is the counterpart of a HashMap and a set is the counterpart of a HashSet. One difference to mention: since Python 3.7 a dict keeps insertion order by rule, while Java's HashMap promises none.
Does a HashSet or HashMap keep insertion order?
Not in Java: both docs say they make no promise about order. If you need insertion order in Java, use a linked variant of the same structures; in Python, a dict already keeps it.
What happens if every key has the same hash code?
All keys land in one bucket or probe path, so in Python each operation compares against the others and degrades toward O(n): in the Python 3.12 set run above, 400 same-hash keys took 93,893 equality checks. Java 8 and later behave better: OpenJDK 21 turns a bucket holding more than 8 entries (TREEIFY_THRESHOLD = 8) into a tree once the table has at least 64 buckets (MIN_TREEIFY_CAPACITY = 64), and the HashMap Javadoc says it "may use comparison order" for Comparable keys, so those cost O(log n).3
Either way a poor hash function turns a fast table into a slow one. This is why hash functions must spread keys evenly; see machine-learning coding rounds and data engineering for places where large deduplication makes this matter.
- A HashMap stores key-value pairs; a HashSet stores distinct keys; Java's HashSet is a HashMap underneath.
- Both give constant-time average add and lookup; the worst case with many collisions is linear.
- Pick the set to deduplicate or test membership, and the map when each key needs a value or a count.
- Neither Java class is synchronized, and neither promises order; Python's dict does keep insertion order.
- In Java a HashSet stores a shared placeholder under every key, so it costs the same per element as a HashMap; at a million keys Python's set is leaner than a dict (the dict container was 25% larger); Java's HashSet is not leaner than its HashMap.
Sources
- HashMap (Java SE 21 API documentation) — Oracle, 24 Oct 2026
- HashSet (Java SE 21 API documentation) — Oracle, 24 Oct 2026
- HashSet.java and HashMap.java (OpenJDK jdk21u source) — OpenJDK, 24 Oct 2026
- Time complexity of operations on built-in types (Python 3 documentation) — Python Software Foundation, 24 Oct 2026
- Built-in types: set types and mapping types (Python 3 documentation) — Python Software Foundation, 24 Oct 2026
