How HashSet Works Internally in Java: A Complete Guide

A Java Set interface represents a group of elements arranged like an array.

• It does not allow duplicate elements.
• When we try to pass the same element that is already available in the Set, then it will not store into the Set.
• It is used to model the mathematical set abstraction.
• You can use it when you want data/Elements with unique items

A Java HashSet class represents a set of elements (objects).

• It does not guarantee the order of elements.
• It is achieved by storing elements as keys with the same value always.
• It constructs a collection that uses a hash table for storing elements.
• It contains unique elements.
• It inherits the AbstractSet class.
• It also implements the Set interface.
• It uses a technique to store elements is called hashing.
• HashSet uses HashMap internally in Java.
• [Important Iterator] HashSet does not have any method to retrieve the object from the HashSet. There is only a way to get objects from the HashSet via Iterator.
• HashSet has default initial capacity = 16.
• HashSet has default loadfactor = 0.75 or 75%
• The capacity may increase automatically when more elements to be store.

Understand the syntax for HashSet.

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

Here you can see <String> that is the generic type parameter representing the type of element storing in the HashSet.

Observe the right side, new HashSet<>() — keep generic type parameter as blank to achieve polymorphism with any of collection including (List, Set, etc.). If you write syntax as below, then you can’t achieve polymorphism. Instantiation will be limited to MyClassA only. Similarly, you can compare for new HashSet<MyClassA>();

List<MyClass> myList = new LinkedList<MyClassA>();

Anyway, let's get back to HashSet,

HashSet uses a constructor HashSet(int capacity) that represents how many elements can be stored in the HashSet.

HashSet uses another constructor HashSet(int capacity, float loadfactor). Here, the loadfactor determines the point where the capacity of HashSet would be increased internally.

For example, the product of capacity and loadfactor is 101*0.5=50.5. It means that after storing the 50th element into the HashSet, its capacity will be internally increased to store more elements.

The initial default capacity of HashSet is 16. The default load factor is 0.75.

import java.util.*;
public class HashSetImplementation {
    public static void main(String[] args) {
        HashSet < String > hs = new HashSet < String > ();
        hs.add("Aabraa");
        hs.add("kaaa");
        hs.add("Daabra");
        System.out.println("Set is " + hs); //view HashSet  
        Iterator it = hs.iterator(); //add an iterator to hs  
        System.out.println("Elements using iterator:");
        while (it.hasNext()) //display elements by using iterator  
        {
            String s = (String) it.next();
            System.out.println(s);
        }
    }
}

Output:

Set is [Aabraa, kaaa, Daabra]
Elements using iterator:
Aabraa
kaaa
Daabra

Let’s say if you are adding similar values to your HashSet, it will keep only unique items. From the above example, if you write the same element N times, then —

hs.add("Daabra");
hs.add("Daabra");

It will show “Daabra” only once a time when we iterate and print it in the console.

Now you must have a question about How HashSet will ignore the duplicates?

When you open the HashSet implementation of the add() method in Java APIs i.e. in rt.jar, You can see the below code.

public class HashSet < E > extends AbstractSet < E > {
    private transient HashMap < E,Object > map;
    // Dummy value to associate with an Object in the backing Map  
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap < > ();
    }
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

HashSet call to add(object) is delegated to put(key, value) internally in the HashMap. Where key is the object we have passed and the value is another object, called PRESENT. It is a constant in java.util.HashSet.

We know that each key is unique in the HashMap. So, we pass the argument in the add(E e) method. Here, we need to associate some value to the key. It will associate with Dummy value that is (new Object()) which is referred by Object reference PRESENT.

When we add an element in HashSet like hs.add(“Daabra”), Java does internally is that it will put that element E here “Daabra” as a key into the HashMap (generated during HashSet object creation). It will also put some dummy value that is Object’s object is passed as a value to the key.

Please note below important points about put(key, value):

• If the Key is unique and added to the map, then it will return null
• If the Key is duplicate, then it will return the old value of the key.
• If the method map.put(key, value) returns null, then the method map.put(e, PRESENT)==null will return true internally, and the element added to the HashSet.
• If the method map.put(key, value) returns the old value of the key, then the method map.put(e, PRESENT)==null will return false internally, and the element will not add to the HashSet.

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

We use iterator() method to retrieve object from the HashSet. It is a method of java.util.HashSet class. It returns iterator for backup Map returned by map.keySet().iterator() method.

I obtain an immense amount of satisfaction from helping others attain their goals and reach their potential through technology. Even if you wish to reach out and say "Hello", I sincerely appreciate all of the wonderful correspondence I receive each day from readers. You all enrich my life, and I hope I am able to do the same for you all as well.

If you find joy and value in what I do, please consider supporting my work with a donation — however much you can afford, it means and helps more than you can imagine.

You can give tips too using Buy me a coffee.

1.  How HashMap Works Internally in Java?

2. Top 45+ Collections Java Interview Questions