How HashSet works in Java
Tags: java, hashset, collection
Published: 2020-05-03 08:55:57

In [core java interview questions](https://javahungry.blogspot.com/2013/09/core-java-coding-programming-questions-answers-technical-interview-java.html), It is common to get bombarded with Collection framework questions. I was interviewed in Goldman Sachs, and there they asked a question where I got dumbstruck. The interviewer asked How do you implement Set in  Java, in other words, the internal working of HashSet or How HashSet works in java. That is, how will make sure each and every element is unique without using Set interfaces or Classes that implements Set Interface.


**Read Also:**   [How HashMap works in java] (https://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html)


I gave the answer, although qualified the interview round as well, the answer is far from satisfactory.

So I came back home and do some research. So finally I got the answer and sharing it with you.


![How HashSet works in Java : JavaHungry](https://4.bp.blogspot.com/-nB-y9BbR83I/W12G2UUGSeI/AAAAAAAAA1A/_zit55j9qBcbEcamS7vcNDsyobqVwUqEgCLcBGAs/s1600/How%2BHashSet%2Bworks%2Bin%2Bjava.jpeg)



















Set Implementation Internally in Java


Each and every element in the set is unique.  So that there is no duplicate elements in the set.


So in java, if we want to add elements in the set then we write code like this


```java
public class JavaHungry {    
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        
        HashSet<Object> hashset = new HashSet<Object>();
        hashset.add(3);
        hashset.add("Java Hungry");
        hashset.add("Blogspot");
        System.out.println("Set is "+hashset);
    }
}
```

It will print the result:       Set is [3, Java Hungry, Blogspot]



Now lets add duplicate element in the above code


```java
public class JavaHungry {
    
    public static void main(String[] args)
    {
        HashSet<Object> hashset = new HashSet<Object>();
        hashset.add(3);
        hashset.add("Java Hungry");
        hashset.add("Blogspot");
        hashset.add(3);                     // duplicate elements
        hashset.add("Java Hungry");              // duplicate elements
        System.out.println("Set is "+hashset);
    }
}
```


It will print the result:       Set is [3, Java Hungry, Blogspot]



Now, what happens internally when you pass duplicate elements in the add() method of the Set object, It will return false and do not add to the HashSet, as the element is already present. So far so good.


But the main problem arises that how it returns false. So here is the answer


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


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

{
    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<>();
    }
    
    // SOME CODE,i.e Other methods in Hash Set
    
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
    
    
    // SOME CODE ,i.e Other methods in Hash Set
}
```


So, we are achieving uniqueness in Set, internally in java through HashMap. Whenever you create an object of HashSet it will create an object of HashMap as you can see in the italic lines in the above code.

We already discussed   [How HashMap works internally in java](https://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html).


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 to the key, so what Java APIs developer did is to pass the Dummy value that is ( new Object () ) which is referred by Object reference PRESENT.


So, actually when you are adding a line in HashSet like HashSet.add(3)   what java does internally is that it will put that element E here 3 as a key in the HashMap(created during HashSet object creation) and some dummy value that is Object's object is passed as a value to the key.


Now if you see the code of the HashMap put(Key k, Value V) method, you will find something like this

```java
 public V put(K key, V value) {

//Some code

}
```

The main point to notice in the above code is that put (key, value) will return


1.  null, if the key is unique and added to the map

2.  Old Value of the key, if the key is duplicate


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

i.e.

```java
   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 the element is added to the HashSet.




So, if the map.put(key, value) returns the old value of the key, then

map.put(e, PRESENT)==null      will return false and the element is not added to the HashSet.


If you still have any doubts then please write in comments.


**Read Also:**   [Best  Books for Learning Java] (https://javahungry.blogspot.com/2014/02/best-books-for-learning-java-must-read.html)