How Set or HashSet works internally in Java

695

Below code illustrated to add data to HashSet

public class Sample{
    
    public static void main(String[] args)
    {
        Set hashset = new HashSet();
        hashset.add(5);
        hashset.add("Hello");
        hashset.add("Java");
        hashset.add(5);
        System.out.println(hashset);
    }
}

the output is: [5, Java, Hello]

Now, we are going to see what happens internally when you pass duplicate elements in the add () method of the Set object.

When you open the HashSet implementation of the add() method in Java API’s that is rt.jar, you will find the following code.

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

{
    private transient HashMap<E,Object> map;

    // it is going to use as a key in the hashmap in the add method

    private static final Object PRESENT = new Object();
    
    public HashSet() {
        map = new HashMap<>();
    }
    // some code here
   
    public boolean add(E e) {
        return map.put(e, PRESENT)  = = null;
    }
     // some code here or other meothods
}

We already know Set accepts only unique elements, internally in java through HashMap. Whenever you create an object of HashSet it will create an object of HashMap in the constructor of HashSet.

As we know in HashMap each key is unique. So what we do in the set is that we pass the argument in the add(Element E) that is E as a key in the HashMap. Now we need to associate some value with the key, so what Java API's developer did is to pass the Dummy value for that key that is which is referred by Object reference PRESENT.

So, actually when you add an element in HashSet like hashset.add(5) what java does internally is that it will put that element E here 5 as a key in the HashMap(created during HashSet object creation) and some dummy value that is the PRESENT object passed as a value to the key.

Now we should recall the functionality of HashMap put(Key k, Value V) method.

 public V put(K key, V value) {

//Some code

}

The main point is in above code when we add some data to the put (key, value) method it will return value object.

HashMap follows Below concept.

  1. null, if the key is unique and added to the map
  2. Old Value of the key, if the key is duplicate

So, add() method of HashSet ,we check the return value of map.put(key,value) method with null value

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

So , if map.put(key,value) returns null ,then map.put(e, PRESENT) == null, will return true and element will add to the HashSet.

So , if map.put(key,value) returns old value of the key ,then map.put(e, PRESENT) == null , will return false and element is not added to the HashSet .