HashSet in Java

If you are learning Java Collections, you will come across the HashSet class. Part of Java’s java.util package, HashSet provides a way to store unique elements in an unordered manner.

If you want to learn Java, enrol in our Free Java Programming Course and upskill today.

What is a HashSet in Java?

A HashSet in Java is a collection that stores unique elements and does not maintain any specific order. It is part of the Java Collections Framework and is implemented using a hash table (specifically, a HashMap).

HashSets are efficient for adding, removing, and checking the presence of elements, providing near constant-time performance on average.

Also Read: What is an Interface in Java?

Features of HashSet

• Unique Elements: A HashSet only stores unique elements. An attempt to add a duplicate element will be ignored.
• Unordered: Elements are not stored in any specific order, and the order may change over time.
• Hash Table: The HashSet uses a hash table, also known as a hash map, internally to store elements.
• Null Value: A HashSet allows only one null value to be stored.
• Non-synchronized: HashSet is not synchronized, meaning it’s not thread-safe.
• Hash Code Based: Elements are stored and identified based on their hash codes.
• Efficient Operations: Basic operations like add, remove, and contains have an average time complexity of O(1), making HashSet efficient for these tasks.

How Does a HashSet Work Internally?

Internally, a HashSet in Java uses a HashMap to store its elements. When you add an element to a HashSet, it’s stored as a key in the HashMap, and a constant value (often PRESENT) is associated with it.

This allows for efficient storage and retrieval of unique elements, as HashMap provides fast lookup based on the hash code of the keys.

1. HashMap as the Underlying Structure: HashSet leverages the HashMap’s efficient storage and retrieval capabilities.

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

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

2. Keys and Values: The elements you add to the HashSet become the keys in the HashMap. A constant value, typically PRESENT (a static final object) is associated with each key.

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

3. Hashing and Buckets: The HashMap uses hashing to determine where elements are stored. The hash code of the element’s key is used to calculate an index into a bucket array (or table) within the HashMap.

int hash = e.hashCode(); // Simplified version
int index = (hash & 0x7FFFFFFF) % bucketArray.length;

4. Collision Handling: If multiple elements have the same hash code, they might end up in the same bucket. The HashMap handles this using techniques like separate chaining (linked lists) to store elements in the same bucket.

// Example of two objects with same hashCode
class Person {
    String name;
    public Person(String name) {
        this.name = name;
    }
    @Override
    public int hashCode() {
        return 42; // forced collision
    }
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Person) {
            return this.name.equals(((Person) obj).name);
        }
        return false;
    }
}

HashSet<Person> set = new HashSet<>();
set.add(new Person("Alice"));
set.add(new Person("Bob")); // Same hashCode -> collision

5. Adding Elements: When you add an element, the hashCode() method is called to get the hash code, which determines the bucket index. The equals() method is used to check for duplicates before adding the element to prevent redundant storage.

public boolean add(E e) {
    // HashMap uses e.hashCode() to find bucket
    // Then uses e.equals() to check for duplicates
    return map.put(e, PRESENT) == null;
}

6. Retrieving Elements: While you can’t directly retrieve elements by their key (since there’s no get() method in HashSet), you can iterate through the elements using an iterator.

Iterator<E> iterator() {
    return map.keySet().iterator();
}

for (E item : set) {
    System.out.println(item); // Uses iterator internally
}

7. No Order: HashSet does not maintain any specific order of elements. They are stored in the HashMap based on their hash codes, so the order of retrieval may not be consistent.

HashSet<String> set = new HashSet<>();
set.add("Banana");
set.add("Apple");
set.add("Cherry");

System.out.println(set); // Output order is not guaranteed

Creating a HashSet in Java

Here’s a simple example to demonstrate how to create and use a HashSet:

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        // Creating a HashSet
        HashSet<String> fruits = new HashSet<>();

        // Adding elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");

        // Adding a duplicate element
        fruits.add("Apple");

        // Displaying the HashSet
        System.out.println("Fruits: " + fruits);

        // Checking if an element exists
        System.out.println("Contains Banana? " + fruits.contains("Banana"));

        // Removing an element
        fruits.remove("Orange");
        System.out.println("After Removal: " + fruits);
    }
}

Output:

Fruits: [Banana, Orange, Apple]
Contains Banana? true
After Removal: [Banana, Apple]

Methods in HashSet

Here are some commonly used methods in the HashSet class:

1. add(E e): If the specified element is not already present in the set, it is added.
2. remove(Object o): Removes the specified element from the set.
3. contains(Object o): It Returns true if the specified element is contained in the set.
4. size(): Returns the number of elements in the set.
5. clear(): Removes all the elements from the set.
6. isEmpty(): Checks if the set is empty.
7. iterator(): It returns an iterator that goes over the elements in the set.

Advantages of HashSet

1. Fast Performance: The hash based storage provides us add, remove, and search operations very efficiently.
2. No Duplicates: Ensures unique elements in the collection.
3. Null Support: Can store a single null value.

Limitations of HashSet

1. No Order Guarantee: HashSet does not preserve the order in which elements are added. Iteration will return elements in an unpredictable, seemingly random order.
2. Potential Performance Degradation: While the average time complexity for operations is O(1), excessive collisions can lead to performance degradation, potentially falling back to O(n) time complexity.
3. Increased Memory Usage: HashSet uses more memory than other collections, especially with poor hash code distribution. Each bucket in the underlying hash table needs to store references to elements, which can consume more memory.
4. Not Thread-Safe: HashSet is not thread-safe, meaning it’s not designed for concurrent access from multiple threads without external synchronization.

Also Read: Synchronization in Java

When to Use HashSet

HashSet should be used when you need to store a collection of unique elements and prioritize fast lookup and retrieval operations, as it uses a hash table for storage. It is a good choice when you need to quickly check if an element exists in a collection or perform set operations like union, intersection, or difference.

It’s particularly useful when you don’t need to maintain the order of elements and don’t need to access elements by their index. 

HashSet vs Other Sets