Java HashSet

Java HashSet

java.util.HashSet<E> is the go-to collection when you need a group of unique elements and fast membership testing. It rejects duplicates automatically, answers contains() in O(1) average time, and requires zero manual duplicate-checking code. Every HashMap, HashSet, and LinkedHashSet you have ever used shares the same internal hash table mechanism — and understanding it is exactly what product company interviewers test.

What Is Java HashSet?

HashSet<E> is a concrete class in java.util that implements the Set<E> interface. A Set enforces one rule above all others: no duplicate elements. Attempting to add an element that already exists returns false silently — no exception, just a no-op.

The diagram below shows where HashSet fits in the Collections hierarchy.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Set<E>              ← uniqueness contract
                    ├── java.util.HashSet<E>   ← backed by HashMap, no order
                    ├── java.util.LinkedHashSet ← backed by LinkedHashMap, insertion order
                    └── java.util.SortedSet<E>
                            └── NavigableSet<E>
                                    └── TreeSet ← backed by TreeMap, sorted order

KEY FACTS:
  Package    : java.util
  Since      : Java 1.2
  Backed by  : HashMap<E, Object> internally
  Ordering   : no guaranteed iteration order
  Null       : allows exactly one null element
  Duplicates : rejected — add() returns false for existing elements
  Thread     : NOT thread-safe
  Initial capacity: 16 buckets (default)
  Load factor     : 0.75 (rehash when 75% full)

The Three Set Implementations Side by Side

FEATURE COMPARISON:

  Feature              HashSet        LinkedHashSet     TreeSet
  -------------------- -------------- ----------------- ---------------
  Order                None           Insertion order   Sorted (natural)
  add() / contains()   O(1) average   O(1) average      O(log n)
  Backed by            HashMap        LinkedHashMap     TreeMap
  Null element         Allowed (1)    Allowed (1)       NOT allowed
  Comparator needed    No             No                Yes (if no Comparable)
  Best for             Fast lookup    Predictable order Sorted iteration

When to Use HashSet

The decision is straightforward once you know what each Set type optimises for.

USE HashSet WHEN:
  - Fast membership testing is the primary operation
    list.contains() is O(n); set.contains() is O(1) average
  - Deduplication — load elements, duplicates disappear automatically
  - Order does not matter at all

USE LinkedHashSet WHEN:
  - Uniqueness is required AND iteration order must match insertion order
  - Processing a stream of events and need to track "seen" items in order

USE TreeSet WHEN:
  - Sorted unique elements are required — first(), last(), floor(), ceiling()
  - Range queries: headSet(), tailSet(), subSet()
  - Elements implement Comparable or you supply a Comparator

USE List.contains() on an ArrayList ONLY WHEN:
  - The list is small (fewer than ~50 elements)
  - You also need index-based access or duplicate elements
  - Switching to a Set would require significant refactoring for marginal gain

The most common production pattern: build a HashSet<String> from a List<String> when contains() will be called many times — list.contains() is O(n), set.contains() is O(1). This single change turns O(n²) loop-contains code into O(n).

How HashSet Works Internally

HashSet is literally a thin wrapper around HashMap. Every element you add to a HashSet becomes a key in a backing HashMap, with a shared dummy Object as the value.

HashSet<String> set = new HashSet<>();
set.add("Java");
set.add("Spring");
set.add("Kafka");

INTERNALLY:
  HashSet fields:
    HashMap<E, Object> map  ← the actual storage
    static final Object PRESENT = new Object()  ← shared dummy value

  Every add(e) call maps to:
    map.put(e, PRESENT)

  After 3 adds, backing map looks like:
    "Java"   → PRESENT
    "Spring" → PRESENT
    "Kafka"  → PRESENT

  contains(e) maps to:
    map.containsKey(e)  ← O(1) average

  remove(e) maps to:
    map.remove(e) != null  ← O(1) average

  add() return value:
    map.put(e, PRESENT) returns null if key was absent (new element)
    map.put(e, PRESENT) returns PRESENT if key already existed (duplicate)
    HashSet.add() returns (put result == null)  → true for new, false for duplicate

The Hash Table Structure

HASHMAP BACKING STORE (default capacity 16):

  table[0]:  null
  table[1]:  Entry("Kafka") → null
  table[2]:  null
  table[3]:  Entry("Java") → Entry("Spring") → null  ← collision chain
  table[4]:  null
  ...
  table[15]: null

  bucket index = (capacity-1) & hash(e.hashCode())

  LOOKUP for "Java":
    1. Compute hash("Java") → find bucket → table[3]
    2. Walk chain: Entry("Java").key.equals("Java") → true → found!
    3. O(1) average — typically one or two comparisons

  ADD duplicate "Java":
    1. hash("Java") → table[3]
    2. Entry("Java").key.equals("Java") → true → key already exists
    3. map.put() returns PRESENT (old value) → add() returns false
    4. No new Entry created — duplicate silently rejected

  REHASH trigger:
    When size > capacity * loadFactor (16 * 0.75 = 12)
    New capacity = 32, all entries redistributed to new buckets — O(n)
    Pre-size: new HashSet<>(expectedSize * 2) to avoid rehashing

The equals() and hashCode() Contract — Critical

HashSet correctness depends entirely on equals() and hashCode() being consistent. Two objects that are logically equal MUST produce the same hash code, or they land in different buckets and the set stores both as "different" elements — violating uniqueness.

CONTRACT VIOLATION EXAMPLE:

  class Product {
      String sku;
      double price;

      @Override
      public boolean equals(Object o) {
          // equals() based on sku only — two Products are same if sku matches
          return o instanceof Product p && sku.equals(p.sku);
      }
      // hashCode() NOT overridden — uses Object's identity hash
  }

  Product p1 = new Product("SKU-001", 999.0);
  Product p2 = new Product("SKU-001", 999.0);

  p1.equals(p2) → true   (same SKU)
  p1.hashCode() → 1829164700  (identity based — different address)
  p2.hashCode() → 1347067481  (identity based — different address)

  HashSet<Product> catalogue = new HashSet<>();
  catalogue.add(p1);  // goes to bucket hash(1829164700) & 15 = bucket 4
  catalogue.add(p2);  // goes to bucket hash(1347067481) & 15 = bucket 11
  catalogue.size() → 2  ← WRONG! Both are the "same" product but stored twice

Core Operations with Examples

add() — Returns Whether Element Was New

add() returns true if the element was not already present and false if it was a duplicate. Using this return value is more efficient than calling contains() first.

Output:
=== Primitive String elements ===
add(java)    : true
add(spring)  : true
add(java)    : false — duplicate
add(null)    : true — one null allowed
add(null)    : false — already there
Set contents : [null, spring, java]
Size         : 3

=== Custom Product elements ===
add(laptop1) : true
add(laptop2) : false — same SKU
add(mouse)   : true
Catalogue    : [Lenovo ThinkPad[SKU-001], Logitech MX[SKU-002]]
Size         : 2

contains(), remove(), and Set Operations

Output:
=== contains() — O(1) average ===
contains(Java)   : true
contains(Python) : false
contains(null)   : false

=== remove() ===
remove(Redis)  : true
remove(Python) : false
After removes  : [Java, Spring, MySQL, Docker, Kafka]

=== Set operations ===
Required  : [Spring, Java, MySQL, Kubernetes]
Candidate : [Spring, Docker, Java, Redis]
Matched skills (intersection)      : [Spring, Java]
Missing skills (required - candidate): [MySQL, Kubernetes]
All skills (union)                 : [Spring, Docker, Java, Redis, MySQL, Kubernetes]

Candidate has all required? : false

Iterating HashSet

Output:
HashSet for-each (no order): Delhi Mumbai Hyderabad Chennai Bengaluru
After removing names > 6 chars: [Mumbai, Delhi]
removeIf equivalent            : [Mumbai, Delhi]

=== Streams on HashSet ===
Numbers      : [33, 3, 22, 19, 7, 8, 41, 15]
Sum of evens : 30
Uppercase    : [MUMBAI, DELHI, HYDERABAD, CHENNAI, BENGALURU]

LinkedHashSet (stable for display): [Mumbai, Delhi, Bengaluru, Chennai, Hyderabad]
TreeSet (sorted)                 : [Bengaluru, Chennai, Delhi, Hyderabad, Mumbai]

Basic Example

Output

true
true
false
Contains Banana: true
Size before remove: 2
After remove: [Apple]

How it works:

1. ›add("Apple") and add("Banana") both return true — the elements are new.
2. ›add("Apple") a second time returns false — HashSet silently rejects the duplicate, and size() stays at 2.
3. ›contains() checks membership in O(1) average time, without scanning the whole collection like a List would.
4. ›remove("Banana") deletes that element, leaving only Apple — showing that a HashSet behaves like a mathematical set: no duplicates, fast lookup, and no guaranteed iteration order.

Performance Considerations

O(1) average vs worst case: The O(1) is average-case. In the absolute worst case — all elements hash to the same bucket — HashSet degrades to O(n) per operation. Java 8 mitigates this with treeification: when a single bucket chain exceeds 8 entries, it converts to a Red-Black tree, limiting worst-case to O(log n) per operation.

Iteration cost: HashSet iteration scans all buckets including empty ones — the cost is O(n + capacity), not just O(n). A HashSet pre-sized to 10,000 that holds 5 elements iterates slowly. Use trimToSize() via the backing map or pre-size correctly: new HashSet<>(expectedSize * 2) to allocate roughly the right number of buckets.

Thread safety: HashSet is not thread-safe. For concurrent set operations, use Collections.newSetFromMap(new ConcurrentHashMap<>()) or CopyOnWriteArraySet (for read-heavy, write-rare scenarios).

Best Practices

Always override both equals() and hashCode() together on classes used as HashSet elements. HashSet uses hashCode() to find the bucket and equals() to confirm the match. Overriding only equals() leaves hashCode() returning identity hashes — two logically equal objects land in different buckets and both get stored, silently violating the uniqueness guarantee. IDEs generate both methods together from selected fields in one action.

Pre-size HashSet for bulk loads of known size. new HashSet<>(expectedSize * 2) allocates approximately the right number of buckets upfront, preventing the O(n) rehash that fires when the set exceeds capacity * 0.75. For loading 10,000 elements, this eliminates multiple full rehash operations.

Prefer Set<E> as the variable type, not HashSet<E>. Set<String> visited = new HashSet<>() lets you swap to LinkedHashSet (for deterministic output) or TreeSet (for sorted output) by changing one line. Declaring HashSet<String> visited = new HashSet<>() couples every method signature to the implementation.

Use set.add(element) return value instead of contains() + add(). if (!set.contains(x)) { set.add(x); } performs two hash table lookups. if (set.add(x)) performs one — add() returns false if the element was already present. One lookup is always faster than two.

Common Mistakes

Mistake 1 — Overriding equals() Without hashCode()

Mistake 2 — Modifying a HashSet Element After Insertion

Mistake 3 — Using HashSet When Order Matters

Mistake 4 — Using List.contains() in a Loop When a Set Would Be O(1)

Interview Questions

Q1. What is HashSet in Java and how does it work internally?

HashSet<E> is a Set implementation that rejects duplicate elements and provides O(1) average add(), remove(), and contains(). Internally, it is backed by a HashMap<E, Object> — every element added to the HashSet becomes a key in the backing map, with a shared static PRESENT object as the value. Duplicate rejection works through HashMap's key uniqueness: map.put(element, PRESENT) returns the old value if the key already exists, and HashSet.add() uses that return value to determine whether the element was new. The hash table uses hashCode() to find the bucket and equals() for exact matching within the bucket.

Q2. Why must equals() and hashCode() be consistent in HashSet?

HashSet uses a two-step lookup: hashCode() identifies the bucket, equals() confirms the exact match. If two logically equal objects produce different hash codes, they land in different buckets — HashSet treats them as distinct and stores both, silently violating the uniqueness guarantee. The contract: if a.equals(b) is true, then a.hashCode() must equal b.hashCode(). The reverse is not required — equal hash codes do not imply equal objects. Classes used as Set elements or Map keys must override both equals() and hashCode() using the same fields.

Q3. What is the difference between HashSet, LinkedHashSet, and TreeSet?

All three implement Set and reject duplicates. HashSet is backed by HashMap — O(1) average for all operations, no guaranteed iteration order. LinkedHashSet extends HashSet and adds a doubly-linked list threading all entries in insertion order — O(1) operations with predictable iteration. TreeSet is backed by TreeMap (Red-Black tree) — O(log n) for all operations, but elements are always iterated in sorted natural order. TreeSet also offers range navigation: first(), last(), floor(), ceiling(), headSet(), tailSet(). Choose HashSet for speed, LinkedHashSet for deterministic order, TreeSet for sorted access.

Q4. Does HashSet allow null elements?

Yes — exactly one null. HashSet places null in bucket 0, bypassing the hashCode() call entirely (which would throw NullPointerException). A second add(null) returns false because the null key already exists in the backing map. TreeSet does not allow null — it calls compareTo() on elements to determine position, and comparing null throws NullPointerException. LinkedHashSet follows HashSet behaviour and allows one null.

Q5. What is the default initial capacity and load factor of HashSet?

The default initial capacity is 16 and the default load factor is 0.75. When size > 16 × 0.75 = 12, the backing HashMap doubles its bucket count to 32 and rehashes all existing entries — an O(n) operation. Subsequent thresholds: 24, 48, 96. For bulk loads of known size, use new HashSet<>(expectedSize * 2) to pre-allocate the right number of buckets and prevent multiple rehash cycles during loading.

Q6. How do you safely remove elements from a HashSet during iteration?

Two patterns: (1) set.removeIf(predicate) — the cleanest Java 8+ approach, handles modCount bookkeeping internally. (2) Explicit iterator.remove() — get the iterator with set.iterator(), call it.next(), then it.remove(). Calling set.remove(element) directly inside a for-each loop throws ConcurrentModificationException because it increments modCount without updating the iterator's expectedModCount. Both removeIf() and iterator.remove() keep the iterator's expected count in sync after each removal.

FAQs

What is the time complexity of HashSet contains() in Java?

O(1) average. HashSet.contains() calls HashMap.containsKey(), which computes hashCode() to find the bucket and then calls equals() on elements in that bucket. With a good hash function and the default load factor of 0.75, most buckets hold at most one or two elements, making the operation effectively constant time. The worst case is O(n) when all elements hash to the same bucket, but Java 8's treeification (converting chains longer than 8 entries to Red-Black trees) limits worst-case to O(log n) for large collision chains.

Can HashSet store duplicate values?

No. HashSet automatically rejects any element that is considered equal to an existing element, as determined by equals() and hashCode(). add() returns false when the element is a duplicate. There is no way to store two "equal" elements — by definition, two equal objects are the same element from the Set's perspective.

What is the difference between HashSet and HashMap in Java?

HashMap<K,V> stores key-value pairs — every entry has a distinct key and an associated value. HashSet<E> stores only elements — there are no values. Internally, HashSet is implemented as a HashMap with a shared dummy object as the value for all keys. The API difference: HashMap uses put(key, value) and get(key); HashSet uses add(element) and contains(element). Use HashMap when each unique key has associated data to look up; use HashSet for pure membership testing and deduplication.

How do you convert a List to a Set to remove duplicates in Java?

new HashSet<>(myList) creates a HashSet containing all unique elements from the list. new LinkedHashSet<>(myList) preserves insertion order while deduplicating. To get back a deduplicated List: new ArrayList<>(new LinkedHashSet<>(myList)). The LinkedHashSet wrapper preserves the first occurrence order, which is usually the desired behaviour for deduplication.

Is HashSet ordered in Java?

No. HashSet makes no guarantee about iteration order — the order depends on hash codes and the internal bucket array structure, and may change between JVM runs or after a rehash triggered by adding more elements. If predictable iteration order is required, use LinkedHashSet (insertion order) or TreeSet (natural sorted order). Never write code that depends on HashSet's iteration order remaining consistent.

What happens when two objects have the same hashCode but are not equal in HashSet?

This is a hash collision — two objects land in the same bucket but are not equal. HashSet handles this correctly: it walks the bucket's chain calling equals() on each entry. Since equals() returns false for both, neither is considered a duplicate of the other, and both are stored in the same bucket as separate entries. Hash collisions are normal and expected — they do not break correctness, they only affect performance (more equals() calls per operation). The problem only arises when equals() returns true but hashCode() returns different values — the objects are in different buckets and cannot find each other.

Summary

HashSet<E> is Java's default choice when you need a collection of unique elements with fast membership testing. Backed by HashMap, it provides O(1) average add(), remove(), and contains(). Duplicates are rejected silently — add() returns false and the collection is unchanged.

Two rules govern HashSet correctness: override both equals() and hashCode() together on element classes, and never mutate a field used in hashCode() after the element is added to the set. Violating either produces silent uniqueness failures that are extremely difficult to diagnose.

For interviews: know the HashMap backing structure, explain the hashCode() → bucket → equals() two-step lookup, contrast HashSet with LinkedHashSet and TreeSet by ordering and performance, and describe how Java 8 treeification protects against collision attacks. These questions come up consistently from fresher rounds at TCS to senior engineering interviews at Flipkart and Razorpay.

What to Read Next