Set in Java: HashSet, LinkedHashSet and TreeSet

What a Set is

A Set is a collection with no duplicates. Adding an element that is already present has no effect and returns false.

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

System.out.println(tags.add("java"));    // true
System.out.println(tags.add("java"));    // false, already present
tags.addAll(List.of("oop", "collections"));

System.out.println(tags.size());         // 3
System.out.println(tags.contains("oop"));
tags.remove("oop");

The three implementations

Set<String> hash = new HashSet<>(List.of("delta", "alpha", "charlie"));
Set<String> linked = new LinkedHashSet<>(List.of("delta", "alpha", "charlie"));
Set<String> tree = new TreeSet<>(List.of("delta", "alpha", "charlie"));

System.out.println(hash);     // some unspecified order
System.out.println(linked);   // [delta, alpha, charlie]
System.out.println(tree);     // [alpha, charlie, delta]

Uniqueness depends on your class

record Tag(String name) { }          // equals and hashCode generated

Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
tags.add(new Tag("java"));
System.out.println(tags.size());     // 1

class BadTag {                        // no equals or hashCode
    private final String name;
    BadTag(String name) { this.name = name; }
}

Set<BadTag> bad = new HashSet<>();
bad.add(new BadTag("java"));
bad.add(new BadTag("java"));
System.out.println(bad.size());       // 2 - identity based, not value based

A HashSet can only detect duplicates if the element type defines equals and hashCode. A TreeSet uses ordering instead, so it needs Comparable or a Comparator, and it treats a comparison result of zero as a duplicate even when equals would disagree.

TreeSet and navigation

NavigableSet<Integer> marks = new TreeSet<>(List.of(35, 48, 62, 79, 91));

System.out.println(marks.first());          // 35
System.out.println(marks.last());           // 91
System.out.println(marks.floor(60));        // 48, greatest at most 60
System.out.println(marks.ceiling(60));      // 62, least at least 60
System.out.println(marks.headSet(62));      // [35, 48]
System.out.println(marks.tailSet(62));      // [62, 79, 91]
System.out.println(marks.subSet(48, 79));   // [48, 62]
System.out.println(marks.descendingSet());  // [91, 79, 62, 48, 35]

Set<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Java");
System.out.println(caseInsensitive.add("java"));   // false, the comparator says equal

LinkedHashSet for deduplication

List<String> withDuplicates = List.of("b", "a", "b", "c", "a");
List<String> unique = new ArrayList<>(new LinkedHashSet<>(withDuplicates));
System.out.println(unique);   // [b, a, c] - duplicates gone, order kept

Set operations

Set<String> a = new HashSet<>(Set.of("java", "sql", "html"));
Set<String> b = Set.of("sql", "css");

Set<String> union = new HashSet<>(a);
union.addAll(b);                 // [java, sql, html, css]

Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b);       // [sql]

Set<String> difference = new HashSet<>(a);
difference.removeAll(b);         // [java, html]

Copy first. These methods modify the set they are called on, which is easy to forget.

Mutable elements break sets

class MutableTag {
    String name;                  // used by equals and hashCode
}

MutableTag tag = new MutableTag();
tag.name = "java";

Set<MutableTag> set = new HashSet<>();
set.add(tag);

tag.name = "sql";                 // the hash changed
System.out.println(set.contains(tag));   // false, although it is in there

Common mistakes

• Adding objects without equals and hashCode and getting duplicates.
• Relying on HashSet iteration order.
• Putting null into a TreeSet, which throws.
• Using a comparator inconsistent with equals, so elements vanish unexpectedly.
• Mutating an element after inserting it.
• Forgetting that retainAll and removeAll modify in place.

Best practices

• Use HashSet by default, LinkedHashSet when order must be predictable, TreeSet when sorting or range queries are needed.
• Make set elements immutable, ideally records.
• Use Set.of(...) for fixed sets.
• Use EnumSet for enum elements.
• Use a Set for membership tests rather than List.contains, which is linear.

Practice

1. Add two equal records to a HashSet and explain the size, then remove hashCode and explain it again.
2. Remove duplicates from a list while preserving order, in one line.
3. Use a TreeSet to find the highest mark not exceeding 70.
4. Why does TreeSet reject null while HashSet accepts one?
5. Compute the union, intersection and difference of two sets without modifying either.

Conclusion

A set gives you uniqueness, and how it decides uniqueness depends on the implementation: hashing and equals for the hash based sets, ordering for TreeSet. Keep elements immutable and the rest follows.