Java Collections

HashSet / TreeSet

Complete lesson for HashSet / TreeSet using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with Java OOP and Collections where relevant.

Basics — HashSet / TreeSet

Section: Java Collections. HashSet, LinkedHashSet, and TreeSet: uniqueness, hashCode/equals, and sorted sets.

Set: no duplicates

HashSet stores unique elements using hashCode and equals. Average O(1) add / contains / remove.
Internally it is a HashMap. One dummy value, keys are your elements.
null is allowed once in HashSet. TreeSet does not allow null with natural ordering.

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

public class HashSetBasics {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("java"); // ignored
        tags.add("dsa");
        System.out.println(tags);
        System.out.println(new TreeSet<>(tags)); // sorted
    }
}

HashSet vs LinkedHashSet vs TreeSet

	`HashSet`	`LinkedHashSet`	`TreeSet`
Order	Undefined	Insertion order	Sorted
Complexity	Average O(1)	Average O(1)	O(log n)
Null	One `null`	One `null`	No (natural order)
Needs	`equals`/`hashCode`	same	`Comparable` or `Comparator`
Use	Membership tests	Unique + stable order	Range queries, sorted view

The equals / hashCode contract

If a.equals(b) then a.hashCode() == b.hashCode(). If you override one, override both.
Equal objects must land in the same bucket. Unequal objects may share a hash (collision) — then equals decides.

Advanced — HashSet / TreeSet

Mutability, TreeSet consistency, and Java 8 buckets

Never mutate a field that participates in hashCode after the object is in a HashSet — the set cannot find it (lost element).
TreeSet uses compare, not equals. If compareTo says 0 but equals is false, the set behaves oddly (contract says they should agree).
Since Java 8, colliding HashMap buckets can treeify (red-black) under certain conditions — worst-case is no longer a long linked list, but you still write a good hashCode.
Set.of(...) rejects duplicates and nulls and is unmodifiable.

Tricky Interview Points

Q1) How does HashSet detect duplicates?

Answer It hashes the object to a bucket, then uses equals against entries in that bucket. Same as HashMap keys.

Q2) HashSet vs TreeSet?

Answer HashSet is unordered O(1) average. TreeSet keeps a sorted order with O(log n) operations and needs a comparison strategy.

Q3) What if you only override equals?

Answer Equal objects can have different hashCodes, go to different buckets, and both appear in the set — duplicates from the user’s point of view.

Q4) Does HashSet keep insertion order?

Answer No. Use LinkedHashSet if you need uniqueness plus insertion order.

Q5) Can two unequal objects have the same hashCode?

Answer Yes. That is a collision. equals then distinguishes them. A constant hashCode is correct but turns the set into O(n).

Q6) Why is a mutable key dangerous?

Answer Changing hashCode after insertion makes the set look in the wrong bucket. contains and remove fail.

Simple Programs

Custom element with equals and hashCode

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

class Point {
    final int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class PointSet {
    public static void main(String[] args) {
        Set<Point> set = new HashSet<>();
        set.add(new Point(1, 2));
        System.out.println(set.add(new Point(1, 2))); // false
        System.out.println(set.contains(new Point(1, 2)));
    }
}

Problem Solving Tricks

Use Set as the variable type; pick Hash/Linked/Tree at construction.
Objects.hash(fields...) is fine for interviews; do not return a constant.
Deduplicate a list with new ArrayList<>(new LinkedHashSet<>(list)) to keep order.
For case-insensitive unique strings, either normalize (toLowerCase) or use a TreeSet with String.CASE_INSENSITIVE_ORDER (remember equals consistency).

Practice Programs List

Remove duplicates from a list while keeping first-seen order (LinkedHashSet).
Put new Point(1,2) twice without hashCode and observe both staying — then add hashCode.
Build a TreeSet of strings and print headSet / tailSet.
Show that HashSet iteration order can differ from insertion order.
Implement isAnagram using two frequency maps or one HashMap plus a HashSet of leftovers.