Internal Working of HashSet

The data structures which implement the set interface guarantee that there would not be any duplication in it i.e; no duplicate lements in that set.

Different implementations of set interface are HashSet, TreeSet, LinkedHashSet etc.

In this article we would look into the internal implementation of the HashSet.

Let’s look into the internal working of the HashSet with the help of coding examples.

import java.util.HashSet;
  
class HashTestImpl
{    
    public static void main(String args[]) 
    {
        HashSet h = new HashSet();
          
        boolean bool1 = h.add("James");//Line 2
        boolean bool2 = h.add("Gosling");//Line 3
        boolean bool3 = h.add("Gosling");//Line 4
        boolean bool4 = h.add("Rocks");//Line 5
          
        System.out.println(bool1);
        System.out.println(bool2);
        System.out.println(bool3);
        System.out.println(bool4);
          
        //Printing all the elements
        System.out.println(h);
              
    }
}

O/P:
true
true
false
true
[James,Gosling,Rocks]

As seen above, we are adding elements to the set in line 2,3,4 & 5.

But in Line 4 we try to add an element which is duplicate. So the add method would return a false and the element would not be added. The final output of that set reflects the same thing.

But how that add method works for the HashSet implementation?Let’s look into the explanation below.

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

If you look into the implementation of the add method of the HashSet class, it is actually internally using an map to store the elements. So the key is the element and value is PRESENT. In hashmap, keys are unique. So if an key already exists when adding then the add method returns the value against the existing key. If it is new, then it returns null.So as per the above method, it would return a true for new additions and false for existing or you can say duplicate elements.

This is the internal working of an HashSet.