StackTipsStackTips

HashSet in Java

The `HashSet` is a collection that uses a hash table for storage. Elements are stored by hashing and as a result, it only supports unique elements.

July 24, 2024 · 13 min read · Updated Sep 2025

The HashSet is a collection that uses a hash table for storage. Elements are stored by hashing and as a result, it only supports unique elements.

Key Properties of HashSet

Unlike most other collections, a HashSet does not keep track of order.

A HashSet is preferred when your data is unique and the order of elements is not required. HashSet performs faster for basic operations like add, remove, and contains, which typically run in constant time, O(1) — but that O(1) depends entirely on your elements having a good hashCode() implementation, which is worth understanding.

How it actually works

HashSet isn't really its own data structure — it's a thin wrapper around a HashMap<E, Object>. Every element you add becomes a key in that backing map, paired with a shared dummy value (a private static final Object PRESENT). add() is really map.put(element, PRESENT), contains() is map.containsKey(element), and so on. Everything about HashSet's performance and behaviour — bucket layout, resizing, treeification of long collision chains — is really HashMap's behaviour. The HashMap article covers that internal mechanism in more depth.

The O(1) average case assumes hashCode() spreads your elements evenly across buckets. A poor hashCode() (or none at all, falling back to Object's identity-based default) that clusters everything into a handful of buckets degrades lookups toward O(n) in the worst case, since Java 8+, an over-full bucket becomes a red-black tree instead of a linked list, capping the true worst case at O(log n) — but you still lose the O(1) you were counting on.

The mutable element trap

This is the single most common HashSet bug: mutate an element's hashCode()-relevant fields after adding it, and the set effectively loses track of it.

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
 
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }
 
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}
 
Set<Point> points = new HashSet<>();
Point p = new Point(1, 2);
points.add(p);
 
p.x = 99; // mutated after insertion
 
System.out.println(points.contains(p)); // false — still stored in the (1,2) bucket, but now hashes to a different one
System.out.println(points.contains(new Point(99, 2))); // also false — that bucket doesn't have this object

p is still physically inside the set — iterating points will print it — but contains() and remove() both recompute the hash from p's current state to find the bucket to look in, and that bucket is no longer where p actually lives. The fix is simple: never use mutable fields in equals()/hashCode() for objects you plan to put in a HashSet or use as a HashMap key. If you need to change something about an object that's already in a set, remove it first, mutate it, then re-add it.

Creating and initializing HashSet

// Creating a HashSet using the default constructor
HashSet<String> hashSet = new HashSet<>();
hashSet.add("A");
hashSet.add("B");
hashSet.add("C");
 
// Creating a HashSet with an initial capacity
HashSet<String> hashSetWithCapacity = new HashSet<>(50);
 
// Creating a HashSet with an initial capacity and load factor
HashSet<String> hashSetWithLoadFactor = new HashSet<>(50, 0.75f);
 
// Creating a HashSet from another collection
List<String> list = Arrays.asList("A", "B", "C", "D");
HashSet<String> hashSetFromList = new HashSet<>(list);