Understand Set, lets see how HashSet works

HashSet uses HashMap internally in Java.HashSet implements Set interface. It guarantees uniqueness. It is achieved by storing elements as keys with the same value always.

When we create an object of HashSet, it internally creates an instance of HashMap with default initial capacity 16.

Lets try adding some elements in HashSet and try iterating it using iterator.

class Student{  
int rollno;  
String name;  
float fee;  
Student(int rollno,String name,float fee){  
rollno=rollno;  
name=name;  
fee=fee;  
}  
void display(){System.out.println(rollno+" "+name+" "+fee);}  
}  
class TestThis1{  
public static void main(String args[]){  
Student s1=new Student(111,"ankit",5000f);  
Student s2=new Student(112,"sumit",6000f);  
s1.display();  
s2.display();  
}}  

Output:

Set is [America, India, Russia]
Elements using iterator:
America
India
Russia

In the above example we have added some duplicate values. We can observe that duplicate values are not stored in the HashSet. 

When we open the HashSet implementation of the add() method in Java APIs i.e. rt.jar, we find the following code in it:

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;  
}  
} 

In the above code a call to add(object) is delegated to put(key, value) internally. 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 are achieving uniqueness in Set internally through HashMap. When we create an object of HashSet, it will create an object of HashMap. 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(“India”), Java does internally is that it will put that element E here “India” 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.

put method of HashMap

put(Key k, Value v)  
{  
//some code  
}  

The important points about put(key, value) method is that:

  • 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.

When we invoke add() method in HashSet, Java internally checks the return value of map.put(key, value) method with the null value.

public boolean add(E e)  
{  
return map.put(e, PRESENT==null);  
}  
  • 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.
How HashSet Works Internally In Java
100% LikesVS
0% Dislikes

Leave a Reply

Your email address will not be published. Required fields are marked *