Home/Learn/Java A–Z/HashSet & LinkedHashSet

HashSet & LinkedHashSet

Intermediate
Collections Framework

Store unique elements with O(1) lookup using HashSet, or preserve insertion order with LinkedHashSet — both backed by the corresponding Map.

Overview

HashSet implements Set by wrapping a HashMap internally — each element is a key in the map, mapped to a dummy value. This means HashSet inherits all of HashMap's performance characteristics: O(1) add, remove, and contains on average, no guaranteed order. LinkedHashSet wraps a LinkedHashMap instead, maintaining insertion order while still providing O(1) operations. Set semantics mean no duplicate elements — equality is determined by equals() and hashCode().

HashSet — Core Operations & Internal Structure

add(E) returns true if the element was newly added, false if it was already present. contains(Object) is O(1) average — this is HashSet's biggest advantage over ArrayList.contains() which is O(n).

Since HashSet is backed by HashMap, all HashMap caveats apply: equals() and hashCode() must be consistent, and performance degrades if hashCode() is poorly implemented (all elements hash to the same bucket).

HashSetDemo.java
import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        // add() returns true on new element, false on duplicate
        System.out.println(set.add("apple"));   // true
        System.out.println(set.add("banana"));  // true
        System.out.println(set.add("apple"));   // false — already present
        System.out.println(set.size());         // 2

        // contains — O(1) average (vs ArrayList O(n))
        System.out.println(set.contains("banana")); // true
        System.out.println(set.contains("cherry")); // false

        // Remove
        set.remove("banana");
        System.out.println(set); // [apple] — order not guaranteed

        // Bulk operations
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4, 5));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6, 7));

        // Union
        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);
        System.out.println(union); // [1, 2, 3, 4, 5, 6, 7]

        // Intersection
        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);
        System.out.println(intersection); // [3, 4, 5]

        // Difference (a - b)
        Set<Integer> diff = new HashSet<>(a);
        diff.removeAll(b);
        System.out.println(diff); // [1, 2]

        // Subset check
        System.out.println(b.containsAll(Set.of(3, 4))); // true
    }
}

LinkedHashSet — Insertion Order

LinkedHashSet extends HashSet and wraps a LinkedHashMap. Every element is stored with a doubly-linked pointer connecting it to the previously inserted element. This adds a small memory and time overhead but guarantees that iteration returns elements in the order they were inserted.

Use LinkedHashSet when you need both uniqueness and predictable iteration order — for example, preserving the order of a de-duplicated list.

LinkedHashSetDemo.java
import java.util.*;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        // HashSet — no guaranteed order
        Set<String> hashSet = new HashSet<>(List.of("banana", "apple", "cherry"));
        System.out.println(hashSet); // [cherry, apple, banana] — unpredictable

        // LinkedHashSet — insertion order guaranteed
        Set<String> linkedSet = new LinkedHashSet<>(List.of("banana", "apple", "cherry"));
        System.out.println(linkedSet); // [banana, apple, cherry] — always insertion order

        // De-duplicate a list while preserving order
        List<String> withDups = List.of("c", "a", "b", "a", "c", "d");
        Set<String>  unique   = new LinkedHashSet<>(withDups);
        List<String> deduped  = new ArrayList<>(unique);
        System.out.println(deduped); // [c, a, b, d] — first occurrences, in order

        // Practical: track visited URLs in order
        Set<String> visited = new LinkedHashSet<>();
        String[] urls = {"/home", "/products", "/home", "/about", "/products"};
        for (String url : urls) visited.add(url);
        System.out.println(visited);
        // [/home, /products, /about] — duplicates removed, order preserved

        // Convert back to List for indexed access
        List<String> visitedList = new ArrayList<>(visited);
        System.out.println(visitedList.get(1)); // /products
    }
}

equals() & hashCode() Contract for Sets

For Set to work correctly, elements must implement equals() and hashCode() consistently: 1. If a.equals(b) → a.hashCode() == b.hashCode() (required) 2. If a.hashCode() == b.hashCode() → a.equals(b) may be true or false (collision)

Mutating an object after adding it to a HashSet can break the set — the element lands in the wrong bucket and the set can no longer find it. Never mutate fields that contribute to hashCode() while the object is in a Set or as a Map key.

SetContractDemo.java
import java.util.*;

public class SetContractDemo {
    static class Point {
        int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }

        @Override public boolean equals(Object o) {
            return o instanceof Point p && p.x == x && p.y == y;
        }
        @Override public int hashCode() { return Objects.hash(x, y); }
        @Override public String toString() { return "(" + x + "," + y + ")"; }
    }

    public static void main(String[] args) {
        Set<Point> points = new HashSet<>();
        Point p = new Point(1, 2);
        points.add(p);

        System.out.println(points.contains(new Point(1, 2))); // true — equals
        System.out.println(points.contains(new Point(1, 2))); // true

        // DANGER: mutate key after adding to set
        p.x = 99;  // changes hashCode — point now in wrong bucket
        System.out.println(points.contains(p));              // false — lost!
        System.out.println(points.contains(new Point(99,2)));// false — lost!
        System.out.println(points.size());                   // 1 — it's still there...
        System.out.println(points); // [(99,2)] — in wrong bucket

        // Moral: use immutable objects as Set elements / Map keys
        record ImmutablePoint(int x, int y) {}
        Set<ImmutablePoint> safePoints = new HashSet<>();
        safePoints.add(new ImmutablePoint(1, 2));
        System.out.println(safePoints.contains(new ImmutablePoint(1, 2))); // true — safe
    }
}

Interactive Visualization

«I»Collection
«I»List
«I»Set
«I»Queue
Collection is the root interface. It branches into List, Set, and Queue.
1 / 5

Key Points to Remember

  • HashSet is backed by HashMap — O(1) add/remove/contains; no guaranteed order
  • LinkedHashSet is backed by LinkedHashMap — same O(1) performance, insertion order preserved
  • add() returns false (not an exception) when a duplicate is detected
  • Set operations: addAll (union), retainAll (intersection), removeAll (difference)
  • Never mutate fields used in hashCode() while an object is stored in a Set or as a Map key
  • Use LinkedHashSet to de-duplicate a list while preserving the order of first appearances

Practice HashSet & LinkedHashSet in the Playground

Run and modify code directly in your browser - no setup needed.

Interview Questions

Sign in to ask Aria
1

What is the internal implementation of HashSet in Java?

MediumAmazon
2

What is the difference between HashSet and LinkedHashSet?

EasyTCS
3

What happens if you add an object to a HashSet and then mutate it?

HardGoogle
4

How do you find the union and intersection of two Sets in Java?

EasyMicrosoft
5

Why should you override both hashCode() and equals() for Set elements?

MediumOracle

Ask Aria about HashSet & LinkedHashSet

Your personal AI tutor — ask anything about this concept

Previous
TreeMap
Next
TreeSet