LuisLlamas Logo
java-sets-hashset-linkedhashset-treeset

Sets in Java: HashSet, LinkedHashSet, and TreeSet

  • 4 min
  • Beginner

A Set is a collection that does not allow duplicate elements according to their equality criteria.

Imagine you are organizing a wedding. You have a guest list in an Excel file (List). By mistake, you have copied and pasted several times, and now “Aunt Paquita” appears four times.

If you send the invitations using the List, Aunt Paquita will receive 4 letters. Bad news. What you need is a structure that says: “If Aunt Paquita is already on the list, ignore the duplicates.”

You need a Set.

What is a set?

A Set is a collection with two sacred rules:

  1. NO duplicates allowed: If you try to add something that already exists (add()), the operation returns false and does nothing.
  2. NO index-based access: There is no get(0) method. You cannot say “give me the first one,” because in a bag of marbles there is no “first” or “second.” You can only ask, “Is the red marble there?” (contains).

The three implementations (the triad)

Java offers us three ways to use Sets. All guarantee uniqueness, but they behave very differently regarding order and speed.

This is the default and most used implementation.

  • Order: None. Elements are left “unordered” (technically, ordered by their internal hash, which seems random to you).
  • Speed: Extremely fast (O(1)) for insertion and search.
  • Usage: When you only want to remove duplicates and don’t care about the order in which the data appears.

It is a HashSet with memory.

  • Order: Maintains the insertion order. If you inserted “A”, then “B”, then “C”, when iterating over it, they will come out as “A, B, C”.
  • Speed: Slightly slower than HashSet (because it has to maintain order pointers).
  • Usage: When you want to avoid duplicates but need the graphical interface to display the data in the same order the user entered them.

Elements are stored in a Red-Black tree.

  • Order: Natural Order (Alphabetical for Strings, numerical for Integers).
  • Speed: The slowest of the three (O(logn)). Inserting costs more because Java has to find the correct spot to maintain alphabetical order in real-time.
  • Usage: When you need the list to be automatically sorted alphabetically at all times.

Comparative example

Let’s insert the same data into the three sets and see what comes out. Data to insert: "Zara", "Ana", "Zara" (duplicate), "Pedro".

import java.util.*;

public class BatallaSets {
    public static void main(String[] args) {
        // 1. HashSet: Total chaos (but fast)
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Zara");
        hashSet.add("Ana");
        hashSet.add("Zara"); // Duplicate ignored
        hashSet.add("Pedro");
        System.out.println("HashSet: " + hashSet);
        // Probable output: [Pedro, Ana, Zara] (Unpredictable order)

        // 2. LinkedHashSet: Insertion order
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("Zara");
        linkedSet.add("Ana");
        linkedSet.add("Pedro");
        System.out.println("LinkedHashSet: " + linkedSet);
        // Guaranteed output: [Zara, Ana, Pedro]

        // 3. TreeSet: Alphabetical order
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Zara");
        treeSet.add("Ana");
        treeSet.add("Pedro");
        System.out.println("TreeSet: " + treeSet);
        // Guaranteed output: [Ana, Pedro, Zara] (Sorted!)
    }
}
Copied!

The pitfall of custom objects (hashCode and equals)

If you use Sets with String or Integer, everything works great. But what happens if you create a Set<User>?

Set<User> usuarios = new HashSet<>();
usuarios.add(new User("Pepe", "1234"));
usuarios.add(new User("Pepe", "1234")); // Is it a duplicate?

System.out.println(usuarios.size()); // Prints 2!
Copied!

Why? For Java, two objects created with new are different in memory, even if they have the same data inside.

For a Set to work correctly with your classes, you MUST override the equals() and hashCode() methods in your User class.

  • equals(): Defines when two users are logically equal (e.g., same ID).
  • hashCode(): Generates an identifier number based on the ID.

Equality contract: If you put your own objects in a HashSet or HashMap, always use your IDE’s automatic generation to create equals and hashCode. If you don’t, uniqueness will not work.

Set operations (mathematical)

Sets are great for performing Venn Diagram operations on a large scale:

Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5));

// UNION (A U B): Everything in A or B
a.addAll(b); // a is now [1, 2, 3, 4, 5]

// INTERSECTION (A ∩ B): Only what is in both
a.retainAll(b); // a would now be [3]

// DIFFERENCE (A - B): What is in A but not in B
a.removeAll(b); // a would now be [1, 2]
Copied!

On this page