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.

Java

Try it out

// File: HashSetAddDemo.java

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class HashSetAddDemo {

    static class Product {
        String sku;
        String name;

        Product(String sku, String name) {
            this.sku  = sku;
            this.name = name;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Product other)) return false;
            return Objects.equals(this.sku, other.sku); // identity = SKU
        }

        @Override
        public int hashCode() {
            return Objects.hash(sku); // must use same field as equals
        }

        @Override
        public String toString() { return name + "[" + sku + "]"; }
    }

    public static void main(String[] args) {

        Set<String> uniqueTags = new HashSet<>();

        // add() returns true for new elements, false for duplicates
        System.out.println("=== Primitive String elements ===");
        System.out.println("add(java)    : " + uniqueTags.add("java"));    // true
        System.out.println("add(spring)  : " + uniqueTags.add("spring"));  // true
        System.out.println("add(java)    : " + uniqueTags.add("java"));    // false — duplicate
        System.out.println("add(null)    : " + uniqueTags.add(null));      // true — one null allowed
        System.out.println("add(null)    : " + uniqueTags.add(null));      // false — already there
        System.out.println("Set contents : " + uniqueTags);
        System.out.println("Size         : " + uniqueTags.size());         // 3, not 5

        System.out.println();

        // Custom object — relies on equals() and hashCode()
        System.out.println("=== Custom Product elements ===");
        Set<Product> catalogue = new HashSet<>();
        Product laptop1 = new Product("SKU-001", "Lenovo ThinkPad");
        Product laptop2 = new Product("SKU-001", "Lenovo ThinkPad"); // same SKU
        Product mouse   = new Product("SKU-002", "Logitech MX");

        System.out.println("add(laptop1) : " + catalogue.add(laptop1));  // true
        System.out.println("add(laptop2) : " + catalogue.add(laptop2));  // false — same SKU
        System.out.println("add(mouse)   : " + catalogue.add(mouse));    // true
        System.out.println("Catalogue    : " + catalogue);
        System.out.println("Size         : " + catalogue.size());        // 2
    }
}

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

Java

Try it out

// File: HashSetOperationsDemo.java

import java.util.HashSet;
import java.util.Set;

public class HashSetOperationsDemo {

    public static void main(String[] args) {

        Set<String> techSkills = new HashSet<>();
        techSkills.add("Java"); techSkills.add("Spring"); techSkills.add("MySQL");
        techSkills.add("Redis"); techSkills.add("Docker"); techSkills.add("Kafka");

        // contains — O(1) average
        System.out.println("=== contains() — O(1) average ===");
        System.out.println("contains(Java)   : " + techSkills.contains("Java"));   // true
        System.out.println("contains(Python) : " + techSkills.contains("Python")); // false
        System.out.println("contains(null)   : " + techSkills.contains(null));     // false

        // remove — O(1) average, returns whether element existed
        System.out.println("\n=== remove() ===");
        System.out.println("remove(Redis)  : " + techSkills.remove("Redis"));   // true
        System.out.println("remove(Python) : " + techSkills.remove("Python")); // false
        System.out.println("After removes  : " + techSkills);

        // Set operations — intersection, union, difference
        Set<String> required = new HashSet<>(Set.of("Java","Spring","MySQL","Kubernetes"));
        Set<String> candidate = new HashSet<>(Set.of("Java","Spring","Docker","Redis"));

        System.out.println("\n=== Set operations ===");
        System.out.println("Required  : " + required);
        System.out.println("Candidate : " + candidate);

        // Intersection — skills candidate has that are required
        Set<String> matched = new HashSet<>(candidate);
        matched.retainAll(required);   // keeps only elements in BOTH sets
        System.out.println("Matched skills (intersection)      : " + matched);

        // Difference — required skills candidate is missing
        Set<String> missing = new HashSet<>(required);
        missing.removeAll(candidate);  // removes elements that appear in candidate
        System.out.println("Missing skills (required - candidate): " + missing);

        // Union — all skills from both
        Set<String> allSkills = new HashSet<>(required);
        allSkills.addAll(candidate);   // adds all — duplicates ignored
        System.out.println("All skills (union)                 : " + allSkills);

        // containsAll
        System.out.println("\nCandidate has all required? : "
            + candidate.containsAll(required)); // false — missing Kubernetes
    }
}

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

Java

Try it out

// File: HashSetIterationDemo.java

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;

public class HashSetIterationDemo {

    public static void main(String[] args) {

        Set<String> cities = new HashSet<>(
            Set.of("Mumbai", "Delhi", "Bengaluru", "Chennai", "Hyderabad")
        );

        // for-each — order unpredictable with HashSet
        System.out.print("HashSet for-each (no order): ");
        for (String city : cities) { System.out.print(city + " "); }
        System.out.println();

        // Iterator — only safe way to remove during traversal
        Set<String> mutable = new HashSet<>(cities);
        Iterator<String> it = mutable.iterator();
        while (it.hasNext()) {
            if (it.next().length() > 6) {
                it.remove(); // safe — no ConcurrentModificationException
            }
        }
        System.out.println("After removing names > 6 chars: " + mutable);

        // removeIf — modern alternative
        Set<String> mutable2 = new HashSet<>(cities);
        mutable2.removeIf(city -> city.length() > 6);
        System.out.println("removeIf equivalent            : " + mutable2);

        // Stream operations on HashSet
        System.out.println("\n=== Streams on HashSet ===");
        Set<Integer> numbers = new HashSet<>(Set.of(15, 3, 22, 8, 41, 7, 33, 19));
        int sumOfEvens = numbers.stream()
            .filter(n -> n % 2 == 0)
            .mapToInt(Integer::intValue)
            .sum();
        System.out.println("Numbers      : " + numbers);
        System.out.println("Sum of evens : " + sumOfEvens);

        // Collecting to a Set via Streams
        Set<String> upperCities = cities.stream()
            .map(String::toUpperCase)
            .collect(Collectors.toSet()); // returns HashSet by default
        System.out.println("Uppercase    : " + upperCities);

        // LinkedHashSet for predictable order
        Set<String> orderedCities = new LinkedHashSet<>(cities);
        System.out.println("\nLinkedHashSet (stable for display): " + orderedCities);

        // TreeSet for sorted order
        Set<String> sortedCities = new TreeSet<>(cities);
        System.out.println("TreeSet (sorted)                 : " + sortedCities);
    }
}

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]

Real-World Example — Flipkart Duplicate Order Filter

A Flipkart order management system receives order events from multiple upstream sources — the mobile app, web platform, and third-party integrations. Each source may emit the same order event more than once due to retries or network duplication. The processor must deduplicate by order ID before writing to the database, and maintain a blacklist of cancelled orders for fast rejection.

Java

Try it out

// File: OrderEvent.java

import java.util.Objects;

public class OrderEvent {

    private final String orderId;
    private final String customerId;
    private final double amount;
    private final String source;

    public OrderEvent(String orderId, String customerId, double amount, String source) {
        this.orderId    = orderId;
        this.customerId = customerId;
        this.amount     = amount;
        this.source     = source;
    }

    public String getOrderId()    { return orderId;    }
    public String getCustomerId() { return customerId; }
    public double getAmount()     { return amount;     }
    public String getSource()     { return source;     }

    // Identity is the orderId — same orderId from different sources is the same order
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof OrderEvent other)) return false;
        return Objects.equals(this.orderId, other.orderId);
    }

    @Override
    public int hashCode() {
        return Objects.hash(orderId);
    }

    @Override
    public String toString() {
        return String.format("[%s] customer=%-8s  Rs.%7.2f  via %s",
            orderId, customerId, amount, source);
    }
}

Java

Try it out

// File: OrderProcessor.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class OrderProcessor {

    // HashSet of processed order IDs — O(1) duplicate check per incoming event
    private final Set<String> processedOrderIds = new HashSet<>();

    // HashSet of cancelled order IDs — O(1) blacklist check
    private final Set<String> cancelledOrderIds = new HashSet<>();

    // Successfully processed orders in order of first receipt
    private final List<OrderEvent> processedOrders = new ArrayList<>();

    public void cancelOrder(String orderId) {
        cancelledOrderIds.add(orderId);
        System.out.println("  CANCELLED: " + orderId);
    }

    public void processEvent(OrderEvent event) {
        String orderId = event.getOrderId();

        // Blacklist check — O(1) via HashSet
        if (cancelledOrderIds.contains(orderId)) {
            System.out.println("  REJECTED (cancelled): " + event);
            return;
        }

        // Duplicate check — O(1) via HashSet
        // add() returns false if orderId was already processed
        if (!processedOrderIds.add(orderId)) {
            System.out.println("  DUPLICATE skipped   : " + event);
            return;
        }

        // New, non-cancelled order — process it
        processedOrders.add(event);
        System.out.println("  PROCESSED           : " + event);
    }

    public void printReport() {
        System.out.println("\n=".repeat(64));
        System.out.printf("  PROCESSING REPORT  (%d unique orders processed)%n",
            processedOrders.size());
        System.out.println("=".repeat(64));
        processedOrders.forEach(o -> System.out.println("  " + o));
        System.out.printf("%n  Total revenue: Rs.%.2f%n",
            processedOrders.stream().mapToDouble(OrderEvent::getAmount).sum());
        System.out.println("=".repeat(64));
    }

    public static void main(String[] args) {

        OrderProcessor processor = new OrderProcessor();

        System.out.println("--- Cancellations registered ---");
        processor.cancelOrder("ORD-004");

        System.out.println("\n--- Incoming order events ---");
        processor.processEvent(new OrderEvent("ORD-001","C-Priya",   1299.0, "Mobile"));
        processor.processEvent(new OrderEvent("ORD-002","C-Rohan",   5499.0, "Web"));
        processor.processEvent(new OrderEvent("ORD-001","C-Priya",   1299.0, "Web"));     // duplicate
        processor.processEvent(new OrderEvent("ORD-003","C-Ananya",  3499.0, "Mobile"));
        processor.processEvent(new OrderEvent("ORD-004","C-Karan",   8999.0, "Mobile"));  // cancelled
        processor.processEvent(new OrderEvent("ORD-002","C-Rohan",   5499.0, "3rdParty"));// duplicate
        processor.processEvent(new OrderEvent("ORD-005","C-Divya",   2199.0, "Web"));
        processor.processEvent(new OrderEvent("ORD-003","C-Ananya",  3499.0, "3rdParty"));// duplicate
        processor.processEvent(new OrderEvent("ORD-004","C-Karan",   8999.0, "Web"));     // cancelled

        processor.printReport();
    }
}

Output:
--- Cancellations registered ---
  CANCELLED: ORD-004

--- Incoming order events ---
  PROCESSED           : [ORD-001] customer=C-Priya    Rs.  1299.00  via Mobile
  PROCESSED           : [ORD-002] customer=C-Rohan    Rs.  5499.00  via Web
  DUPLICATE skipped   : [ORD-001] customer=C-Priya    Rs.  1299.00  via Web
  PROCESSED           : [ORD-003] customer=C-Ananya   Rs.  3499.00  via Mobile
  REJECTED (cancelled): [ORD-004] customer=C-Karan    Rs.  8999.00  via Mobile
  DUPLICATE skipped   : [ORD-002] customer=C-Rohan    Rs.  5499.00  via 3rdParty
  PROCESSED           : [ORD-005] customer=C-Divya    Rs.  2199.00  via Web
  DUPLICATE skipped   : [ORD-003] customer=C-Ananya   Rs.  3499.00  via 3rdParty
  REJECTED (cancelled): [ORD-004] customer=C-Karan    Rs.  8999.00  via Web

================================================================
  PROCESSING REPORT  (4 unique orders processed)
================================================================
  [ORD-001] customer=C-Priya    Rs.  1299.00  via Mobile
  [ORD-002] customer=C-Rohan    Rs.  5499.00  via Web
  [ORD-003] customer=C-Ananya   Rs.  3499.00  via Mobile
  [ORD-005] customer=C-Divya    Rs.  2199.00  via Web

  Total revenue: Rs.12496.00
================================================================

Both processedOrderIds and cancelledOrderIds are HashSet<String> — each contains() and add() call is O(1) regardless of how many orders have been processed. Replacing either with a List would make those checks O(n), creating an O(n²) processor that degrades visibly at scale.

Performance Considerations

Operation	HashSet	LinkedHashSet	TreeSet
add(e)	O(1) average	O(1) average	O(log n)
remove(e)	O(1) average	O(1) average	O(log n)
contains(e)	O(1) average	O(1) average	O(log n)
Iteration	O(n + capacity)	O(n)	O(n)
first() / last()	Not available	Not available	O(log n)
floor() / ceiling()	Not available	Not available	O(log n)
Memory per element	Moderate (HashMap Node)	Higher (+ linked list)	Higher (+ tree pointers)

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()

Java

Try it out

class Employee {
    String employeeId;
    String name;

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Employee other)) return false;
        return Objects.equals(this.employeeId, other.employeeId);
    }
    // hashCode() NOT overridden — uses Object identity hash

    // Consequence:
    // Employee e1 = new Employee("E-001", "Priya");
    // Employee e2 = new Employee("E-001", "Priya");
    // set.add(e1); set.add(e2);
    // set.size() → 2  — both stored, contract violated
}

Mistake 2 — Modifying a HashSet Element After Insertion

Java

Try it out

// WRONG — mutating a field used in hashCode() after insertion loses the element
class Tag {
    String value;
    Tag(String v) { this.value = v; }

    @Override public boolean equals(Object o) { return o instanceof Tag t && value.equals(t.value); }
    @Override public int hashCode() { return Objects.hash(value); }
}

Set<Tag> tags = new HashSet<>();
Tag t = new Tag("java");
tags.add(t);            // goes into bucket for hash("java")

t.value = "kotlin";     // hash changes! element is now "lost" in old bucket

tags.contains(t);       // false — element is in wrong bucket for hash("kotlin")
tags.size();            // 1 — element is still there but unreachable
// tags is now permanently inconsistent

// Fix: use immutable fields in equals/hashCode, or use immutable types as Set elements

Mistake 3 — Using HashSet When Order Matters

Java

Try it out

Set<String> steps = new HashSet<>();
steps.add("Step 1: Validate");
steps.add("Step 2: Process");
steps.add("Step 3: Confirm");

// WRONG assumption: iteration will follow insertion order
for (String step : steps) {
    System.out.println(step); // order is undefined — may print Step 3 before Step 1
}

// CORRECT — use LinkedHashSet for insertion-order iteration
Set<String> orderedSteps = new LinkedHashSet<>();
orderedSteps.add("Step 1: Validate");
orderedSteps.add("Step 2: Process");
orderedSteps.add("Step 3: Confirm");
// Now iteration always follows insertion order

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

Java

Try it out

List<String> processedIds = new ArrayList<>();

// WRONG — O(n) per contains call — total loop is O(n²)
for (String incomingId : incomingIds) {
    if (!processedIds.contains(incomingId)) {  // scans entire list every time
        processedIds.add(incomingId);
        process(incomingId);
    }
}

// CORRECT — O(1) per add call — total loop is O(n)
Set<String> processedIds = new HashSet<>();
for (String incomingId : incomingIds) {
    if (processedIds.add(incomingId)) { // false if already present — no double call
        process(incomingId);
    }
}

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

Continue Learning Collections Framework

Next Step

LinkedHashSet

Learn a HashSet that also remembers insertion order.

→

forEach()

Learn how to run an action on every element in a Stream.

→

TreeMap

Learn a Map that keeps its keys sorted automatically.

→

LinkedList Internal Working

See exactly how LinkedList works internally.