HashSet in Java – A Detailed Tutorial

If you are learning Java and exploring the Java Collection Framework, then one of the most important classes you must understand is the HashSet. It’s a part of the Set interface, and it’s widely used when you want to store unique elements with no duplicates and when ordering does not matter.

Let’s dive in

What is a HashSet?

HashSet is a class in Java that implements the Set interface and uses a Hash Table to store elements.

The key point is:

• A HashSet does not allow duplicate elements and does not maintain insertion order.
• It belongs to java.util package and is available since Java 1.2.

Key Characteristics of HashSet

Feature	Description
Duplicate elements	❌ Not allowed
Null values	✅ Allows one null
Order	❌ Not preserved
Thread-safe	❌ Not synchronized
Backed by	HashMap
Performance	Fast for search, add, and remove operations

How HashSet Works Internally

Internally, HashSet uses a HashMap to store elements. When you add an element to a HashSet, it is actually stored as a key in the underlying HashMap with a dummy value like PRESENT.

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

What happens when you add an element?

• It calculates the hashcode of the element.
• The hashcode decides the bucket in the HashMap.
• If no duplicate is found in that bucket (based on equals() and hashCode()), it stores the element.

Below is further indepth explanations of the HashSet Internal Working

Internal Code (Simplified)

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    
    private transient HashMap<E, Object> map;

    // Dummy object to act as value for all keys in the map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

Step-by-Step: What Happens When You Call add()?

Let’s say:

HashSet<String> set = new HashSet<>();
set.add("apple");

Step 1: HashSet calls map.put(“apple”, PRESENT)

You’re adding "apple" to the HashSet, but internally this means putting the key “apple” and value PRESENT into the HashMap.

Step 2: Calculate HashCode

• HashMap first calculates the hashCode() of "apple".

int hash = "apple".hashCode();

Let’s say the hash of "apple" is 93029210.

Step 3: Find Bucket (Index) using Hash

HashMap calculates the bucket index from the hash:

int index = hash % capacity;  // e.g., capacity is 16

Suppose:

index = 93029210 % 16 = 2

So, "apple" will be attempted to be placed in bucket 2.

Step 4: Check for Duplicates

Before adding, it checks:

• Is any existing key in bucket 2 equal to "apple"?
• This uses equals() to compare keys in the same bucket.

If no such key is found (i.e., "apple" is not already there), it adds the key-value pair.

Step 5: Store the Element

If it’s not a duplicate, it stores:

map.put("apple", PRESENT);

Now, the HashMap inside the HashSet looks like:

{ "apple" => PRESENT }

What If You Add the Same Element Again?

set.add("apple");

Now:

• "apple".hashCode() is the same
• Same bucket is checked
• equals() finds the existing "apple" already present
• So, no insertion is done
• add() returns false

Summary of HashSet Internal Working

Step	Action
1.	Compute hashCode() of the element
2.	Determine bucket index using hash
3.	Check bucket for existing element using equals()
4.	If not found, add element as key to HashMap with value PRESENT
5.	If duplicate, do nothing

Constructors in HashSet

The HashSet class in Java provides several constructors to initialize the set in different ways. Internally, all these constructors initialize a backing HashMap.

1. HashSet()

HashSet<E> hs = new HashSet<>();

• Description: Creates an empty HashSet with default initial capacity 16 and load factor 0.75.
• Use Case: Use when you don’t know how many elements will be added initially.

Example:

HashSet<String> fruits = new HashSet<>();

2. HashSet(int initialCapacity)

HashSet<E> hs = new HashSet<>(int initialCapacity);

• Description: Creates a HashSet with the specified initial capacity, default load factor 0.75.
• Use Case: Use this constructor if you know approximately how many elements you’ll add, to reduce rehashing.

Example:

HashSet<String> cities = new HashSet<>(100);  // capacity for 100 elements

3. HashSet(int initialCapacity, float loadFactor)

HashSet<E> hs = new HashSet<>(int initialCapacity, float loadFactor);

• Description: Creates a HashSet with specified capacity and load factor.
• Load Factor: Determines when to resize (rehash). If number of elements exceeds (capacity * loadFactor), it resizes.
• Use Case: Advanced use where you want to control memory usage and performance.

Example:

HashSet<Integer> ids = new HashSet<>(50, 0.5f);

4. HashSet(Collection<? extends E> c)

HashSet<E> hs = new HashSet<>(Collection<? extends E> c);

• Description: Creates a HashSet and adds all elements from the given collection, ensuring uniqueness.
• Use Case: Convert a list or any other collection to a HashSet.

Example:

List<String> names = Arrays.asList("Alice", "Bob", "Alice", "Charlie");
HashSet<String> uniqueNames = new HashSet<>(names);
System.out.println(uniqueNames); // [Alice, Bob, Charlie]

Java Program: HashSet Example with Explanations

import java.util.HashSet;
import java.util.Iterator;

public class HashSetDemo {
    public static void main(String[] args) {

        // 1. Create a HashSet of Strings
        HashSet<String> fruits = new HashSet<>();

        // 2. Add elements to the HashSet
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Mango");
        fruits.add("Apple");   // Duplicate value

        // 3. Display the elements
        System.out.println("Fruits in HashSet: " + fruits);

        // 4. Check if a particular element exists
        if (fruits.contains("Banana")) {
            System.out.println("Banana is in the set.");
        }

        // 5. Remove an element
        fruits.remove("Mango");
        System.out.println("After removing Mango: " + fruits);

        // 6. Size of the set
        System.out.println("Total number of fruits: " + fruits.size());

        // 7. Iterate using Iterator
        System.out.println("Iterating over HashSet:");
        Iterator<String> iterator = fruits.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        // 8. Clear the set
        fruits.clear();
        System.out.println("Is HashSet empty after clear()? " + fruits.isEmpty());
    }
}

Output

Fruits in HashSet: [Apple, Banana, Mango]
Banana is in the set.
After removing Mango: [Apple, Banana]
Total number of fruits: 2
Iterating over HashSet:
Apple
Banana
Is HashSet empty after clear()? true

Note: Output order may vary because HashSet does not maintain insertion order.

Step-by-Step Program Explanation

1. Creating a HashSet

HashSet<String> fruits = new HashSet<>();

Creates a new empty HashSet of type String.

2. Adding Elements

fruits.add("Apple");
fruits.add("Banana");
fruits.add("Mango");
fruits.add("Apple");

• Adds 3 unique fruits.
• The second "Apple" is ignored because HashSet does not allow duplicates.

3. Printing the HashSet

System.out.println("Fruits in HashSet: " + fruits);

Prints all the unique elements.

4. Checking if an Element Exists

fruits.contains("Banana");

Returns true if “Banana” is present.

5. Removing an Element

fruits.remove("Mango");

Deletes “Mango” from the set.

6. Getting Size

fruits.size();

Returns the number of elements currently in the set.

7. Iterating Through the HashSet

Iterator<String> iterator = fruits.iterator();

Iterates through the set using an Iterator.

8. Clearing the Set

fruits.clear();

Removes all elements from the set.

Notice that Apple was added twice, but it only appears once.

Commonly Used Methods in HashSet

Method	Description
add(E e)	Adds element
remove(Object o)	Removes element
contains(Object o)	Checks existence
size()	Returns size
isEmpty()	Checks if empty
clear()	Clears all elements
iterator()	Returns iterator to loop
addAll(Collection c)	Adds all elements from another collection

Example with HashSet Methods

1. add(E e)

Purpose: Adds the specified element to the set if it is not already present.

HashSet<String> cities = new HashSet<>();
cities.add("Delhi");
cities.add("Mumbai");
cities.add("Delhi"); // Duplicate

System.out.println(cities); // Output: [Delhi, Mumbai]

📝 Duplicates are not added.

2. contains(Object o)

Purpose: Checks if the set contains the specified element.

System.out.println(cities.contains("Mumbai")); // true
System.out.println(cities.contains("Chennai")); // false

3. remove(Object o)

Purpose: Removes the specified element from the set if present.

cities.remove("Delhi");
System.out.println(cities); // Output: [Mumbai]

4. size()

Purpose: Returns the number of elements in the set.

System.out.println("Total cities: " + cities.size()); // 1

5. isEmpty()

Purpose: Checks if the set is empty.

System.out.println("Is set empty? " + cities.isEmpty()); // false

6. clear()

Purpose: Removes all elements from the set.

cities.clear();
System.out.println("After clear: " + cities); // []

7. iterator()

Purpose: Returns an iterator to loop through elements.

HashSet<String> fruits = new HashSet<>(Arrays.asList("Apple", "Mango", "Banana"));

Iterator<String> it = fruits.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

8. addAll(Collection<? extends E> c)

Purpose: Adds all elements from the specified collection.

HashSet<String> setA = new HashSet<>(Arrays.asList("Python", "Java"));
HashSet<String> setB = new HashSet<>(Arrays.asList("C++", "JavaScript"));

setA.addAll(setB);
System.out.println(setA); // Output: [Python, Java, C++, JavaScript]

9. retainAll(Collection<?> c)

Purpose: Keeps only elements that are also in the specified collection.

HashSet<String> set1 = new HashSet<>(Arrays.asList("Cat", "Dog", "Cow"));
HashSet<String> set2 = new HashSet<>(Arrays.asList("Cow", "Goat"));

set1.retainAll(set2);
System.out.println(set1); // Output: [Cow]

10. removeAll(Collection<?> c)

Purpose: Removes all elements that exist in the specified collection.

HashSet<Integer> numbers = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
numbers.removeAll(Arrays.asList(2, 3));

System.out.println(numbers); // Output: [1, 4, 5]

11. equals(Object o)

Purpose: Compares two sets for equality.

HashSet<String> a = new HashSet<>(Arrays.asList("X", "Y"));
HashSet<String> b = new HashSet<>(Arrays.asList("Y", "X"));

System.out.println(a.equals(b)); // true

📝 Order doesn’t matter in sets.

12. toArray()

Purpose: Converts the set into an array.

HashSet<String> animals = new HashSet<>(Arrays.asList("Lion", "Tiger", "Bear"));
Object[] arr = animals.toArray();

System.out.println(Arrays.toString(arr)); // Example: [Lion, Tiger, Bear]

Iterating a HashSet Using for Loop and Iterator

Note to Add: You can iterate over a HashSet using a regular for loop only after converting it to an array, because HashSet doesn’t support direct index access.

Iterating using for Loop

import java.util.*;

class Student {
    int id;
    String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    // To ensure uniqueness based on student ID
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student)) return false;
        Student s = (Student) o;
        return id == s.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Student{id=" + id + ", name='" + name + "'}";
    }
}

public class HashSetLoopExample {
    public static void main(String[] args) {
        HashSet<Student> studentSet = new HashSet<>();

        studentSet.add(new Student(101, "Alice"));
        studentSet.add(new Student(102, "Bob"));
        studentSet.add(new Student(103, "Charlie"));
        studentSet.add(new Student(101, "Alice Duplicate")); // Won't be added due to same ID

        // 🔁 Iterating using a traditional for loop (via toArray())
        System.out.println("Using traditional for loop:");
        Student[] studentArray = studentSet.toArray(new Student[0]);
        for (int i = 0; i < studentArray.length; i++) {
            System.out.println(studentArray[i]);
        }
    }
}

Output

Using traditional for loop:
Student{id=101, name='Alice'}
Student{id=102, name='Bob'}
Student{id=103, name='Charlie'} 

Points to Add: Iterating a HashSet Using for Loop

1. HashSet Doesn’t Support Index-Based Access:
   • HashSet does not maintain any order or allow access via an index.
   • You cannot directly use a classic for loop with index (for (int i = 0; i < ...; i++)) unless you convert it to an array or list.
2. Use toArray() to Convert:
   • Convert the HashSet to an array using: Object[] array = set.toArray(); or a typed array: Type[] array = set.toArray(new Type[0]);
3. Allows Indexed Access in Loops:
   • Once converted to an array, you can use a traditional for loop to access elements by index.
   • This is useful when you want to print the element number or loop in reverse (which you can’t do directly with a HashSet).
4. Order is Not Guaranteed:
   • Since HashSet is unordered, the element order in the array may not match the insertion order.
   • If you need insertion order, use LinkedHashSet instead.
5. Useful in Specific Scenarios:
   • Index-based processing like assigning IDs ("Student 1: ...") or formatting output.
   • When working with APIs or methods that require arrays.

Iterating using Iterator

Note to Add: Iterator is preferred when you need safe removal of elements during iteration or when dealing with any generic collection.

import java.util.*;

class Student {
    int id;
    String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    // To ensure uniqueness based on student ID
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student)) return false;
        Student s = (Student) o;
        return id == s.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Student{id=" + id + ", name='" + name + "'}";
    }
}

public class HashSetLoopExample {
    public static void main(String[] args) {
        HashSet<Student> studentSet = new HashSet<>();

        studentSet.add(new Student(101, "Alice"));
        studentSet.add(new Student(102, "Bob"));
        studentSet.add(new Student(103, "Charlie"));
        studentSet.add(new Student(101, "Alice Duplicate")); // Won't be added due to same ID

        // 🔁 Iterating using Iterator
        System.out.println("\nUsing Iterator:");
        Iterator<Student> iterator = studentSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

Output

Using Iterator:
Student{id=101, name='Alice'}
Student{id=102, name='Bob'}
Student{id=103, name='Charlie'}

Points to Add: Iterating a HashSet Using Iterator

1. Standard Way to Traverse Any Collection:
   • Iterator is a universal and standard way to iterate over collections like HashSet, ArrayList, etc.
2. Supports Only Forward Traversal:
   • Iterator for HashSet allows only forward iteration, one element at a time.
   • If you need backward traversal, use ListIterator (only available for List, not Set).
3. Method Used – iterator():
   • You can get an Iterator object from the set: Iterator<Type> it = set.iterator();
4. Has Two Main Methods:
   • hasNext(): Checks if there’s another element.
   • next(): Returns the next element in the iteration.
5. Safe Removal During Iteration:
   • Unlike a for-each loop, Iterator allows removing elements safely during iteration using: it.remove();
6. No Index Involved:
   • Iterator does not require indexing, making it ideal for unordered structures like HashSet.
7. Prevents ConcurrentModificationException (if used correctly):
   • Direct modification of the set during iteration (like set.remove()) will throw ConcurrentModificationException.
   • Using it.remove() avoids this issue.

Time Complexity of HashSet

Operation	Time Complexity
Add	O(1) average
Remove	O(1) average
Contains	O(1) average
Iteration	O(n)

Worst-case complexity can go up to O(n) if hash collisions occur frequently.

When to Use HashSet?

• When you want to store unique elements only
• When insertion order doesn’t matter
• When you need fast search, insert, and delete

Difference Between HashSet, LinkedHashSet, TreeSet

Feature	HashSet	LinkedHashSet	TreeSet
Order	Unordered	Insertion order	Sorted
Performance	Fastest	Slower than HashSet	Slowest
Null elements	1 allowed	1 allowed	❌ Not allowed
Backed by	HashMap	LinkedHashMap	TreeMap

Real-World Examples

• Keeping a set of visited URLs in a web crawler.
• Removing duplicate entries from a list of emails or names.
• Tracking unique user IDs in a session.

Common Interview Questions

1. Why does HashSet not allow duplicates?
   • Because it uses HashMap where keys are unique.
2. Can HashSet store null?
   • Yes, but only one null.
3. What happens if we don’t override equals() and hashCode() in custom class?
   • HashSet may treat duplicates as different elements.
4. How to maintain order in a Set?
   • Use LinkedHashSet.

Summary

• HashSet is part of Java Collections used to store unique elements.
• It is based on a HashMap and provides constant-time performance for basic operations.
• Does not maintain insertion order.
• Allows only one null.
• Ideal for cases where uniqueness and speed matter more than order.