What is a HashSet in Java and what guarantees does it provide about element ordering and uniqueness?
answer
- Backed by a HashMap, element = key, value = shared dummy
- No ordering guarantee; order can change on rehash
- Average O(1) add/remove/contains
- Uniqueness via equals() + hashCode()
- Allows one null
basics
~10 sA HashSet is a collection that stores unique elements with no duplicates. It does not keep elements in any particular order, and you cannot rely on the order when you iterate over it.
solid answer
~40 sA HashSet is Java's implementation of the Set interface that stores unique elements. It is backed internally by a HashMap: each element you add becomes a key in that map, with a shared dummy object as the value, so duplicate keys (elements) are silently rejected. Because of this, add, remove, and contains run in average O(1) time. HashSet gives no ordering guarantee at all: the iteration order depends on hash codes and the internal bucket layout, and it can change as the set grows and rehashes. It permits a single null element. If you need predictable iteration you reach for LinkedHashSet (insertion order) or TreeSet (sorted order). Uniqueness is decided by the elements' equals() and hashCode() methods, not by reference identity.
code
java · 9 linesSet<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("apple"); // duplicate, ignored
System.out.println(fruits.size()); // 2
System.out.println(fruits.contains("apple")); // true (average O(1))
// Iteration order is unspecified — do NOT rely on it:
for (String f : fruits) System.out.println(f);go deeper
Knows HashSet stores unique elements with no guaranteed order and offers fast lookups.
Can explain it is backed by a HashMap (element as key), the average O(1) operations, and the single-null rule.
Articulates the hashCode/equals bucket mechanism, rehashing's effect on order, and the worst-case collision behaviour.
Reasons about memory/throughput trade-offs versus other Set impls and when iteration-order or sorted semantics justify a different structure across a codebase's conventions.
## What problem a Set solves A **Set** is a collection that holds **no duplicate elements** — like the mathematical idea of a set. If you try to add something that is already there, nothing changes. This is different from a **List**, which allows duplicates and keeps a positional order. Java's `java.util.Set` is an interface (a contract). `HashSet` is the most common concrete class that fulfils that contract. ## How HashSet actually works inside HashSet does not invent its own storage. It **wraps a `HashMap`**. A HashMap stores **key → value** pairs and guarantees the keys are unique. HashSet exploits that: when you call `set.add("apple")`, internally it does `map.put("apple", PRESENT)`, where `PRESENT` is a single shared dummy `Object` reused for every entry (so it wastes no extra memory per element). The element you care about is stored as the **key**; the value is throwaway. Because HashMap keys are unique, HashSet elements are automatically unique — HashSet inherits uniqueness for free. ## Hashing in one paragraph A **hash code** is an `int` produced by an object's `hashCode()` method. The map uses it to decide which **bucket** (slot in an internal array) the element lands in: roughly `bucketIndex = hash & (arrayLength - 1)`. Many objects can share a bucket (a **collision**); within a bucket they are compared with `equals()`. So: - `hashCode()` finds the bucket quickly. - `equals()` confirms exact identity within that bucket. This two-step lookup is why `contains`, `add`, and `remove` are **average O(1)** — constant time, independent of the set's size — instead of scanning every element. ## Ordering: the key takeaway HashSet gives **no ordering guarantee**. The order you see when iterating is an artefact of hash codes and bucket placement, and it can change when the set **rehashes** (rebuilds its internal array as it grows). Never write code that depends on HashSet iteration order. ## Nulls HashSet permits exactly **one `null`** element (because HashMap permits one null key). ## When to use it Reach for HashSet when you need fast membership tests and de-duplication and you do **not** care about order. If you need insertion order, use `LinkedHashSet`; if you need sorted order, use `TreeSet`.
- Why does HashSet allow only one null element?Because it is backed by a HashMap, which permits a single null key. The null is hashed to bucket 0 by special-case handling. A second null would be a duplicate key and is ignored.
- What is the time complexity of contains() on a HashSet and why?Average O(1): hashCode() picks a bucket directly and equals() checks the few elements in that bucket. Worst case is O(n) if all elements collide into one bucket, though modern HashMap turns long collision chains into balanced trees, bounding it to O(log n).
Think of a coat-check room with numbered hooks. The hash code tells you which hook to go to instantly; if two coats share a hook you compare them by hand (equals). You never get your coats back in the order you handed them in.
saying these in an interview costs you the question
- Claiming HashSet preserves insertion order
- Saying HashSet is sorted (that's TreeSet)
- Believing add/contains are O(n) in the common case
- Thinking uniqueness is based on == reference equality rather than equals()/hashCode()