HashSet Internal Working : How HashSet ensure Uniqueness

HashSet is an implementation of Set interface in Java which means in Set duplicate elements can not be added. If we try to add duplicate element then HashSet will discard the newly duplicated element to be added. But the question is How HashSet does that , How does it find out about the duplicate element and discard it from getting added.

Let's see the internal working of HashSet to find the asnwer.

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.

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 .

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(Elemene 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 .

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

public V put(K key, V value) {
     //Some code
}
The main point to notice in above code is that put (key,value) will return

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

So , in HashSet add() method ,  we check the return value of map.put(key,value) method with null value i.e.
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 is added 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 .

This covers the concept of internal working of HashSet , if you have any questions or you want to add anything then please comment below.

Comments

Post a Comment

Popular posts from this blog

Deploy standalone Spring MVC Application in Docker Container

Image
In this post we will deploy simple standalone spring mvc application in Docker container. If you want to deploy the spring boot application in docker container, you can check my post Containerize Spring Boot application using Docker   . We know that in spring boot application there is embed Tomcat application server and run our app on top of it but in case of standalone spring mvc application we don't have embed Tomcat server , hence we need to deploy the application in explicit tomcat standalone server. Process to deploy the spring mvc in docker container : 1) First we need to get the Tomcat image. 2) Second to deploy the war in tomcat we need to save it in tomcat webapps direcory. Create Docker file  FROM : Using docker FROM command we are fetching the tomcat image from the Docker Hub. COPY : In the second line we are copying the war file in tomcat webapp directory. Note :  Any war saved in the tomcat webapps folder will be installed on tomcat start up. Yo
Read more

Refactor Code : Separate Query from Modifier

In this post we will learn about the one of the important code refactoring algorithm "Separate Query from Modifier" .When you have a method that gives you a value and has no observable side effects, you have a lot less to worry. You can move the call to other places in this method freely. A good rule to follow is to say that any method that returns a value should not have other observable side effects.  You have a method that returns a value but also changes the state of an object . Create two method, one for the query and one for the modification. We first take the example of the below and will find out what is wrong with this code and refactor it. In the above , method findMiscreant(List<Person> people) signifies that its responsibility will be to find miscreant only. But if we give clear look to the method , apart from finding Miscreant , it is sending some notification as   SendAlert()  to other system . Hence we can easily see that this method is doi
Read more

ConcurrentHashMap Internal Working

Image
ConcurrentHashMap utilizes the same principles of HashMap, but is designed primarily for a multi-threaded application and hence it does not require explicit synchronization.   The only thread safe collection objects were Hashtable and synchronized Map prior to JDK 5. Before learning How ConcurrentHashMap works in Java , we need to look at why concurrentHashMap is added to the Java SDK. Why we need ConcurrentHashMap when we already had Hashtable ? Hashtable provides concurrent access to the Map.Entries objects by locking the entire map to perform any sort of operation (update,delete,read,create). Suppose we have a web application , the overhead created by Hashtable  (locking the entire map) can be ignored under normal load. But under heavy load , the overhead of locking the entire map may prove fatal and may lead to delay response time and   overtaxing of the server. This  is where ConcurrentHashMap comes to rescue. According to ConcurrentHashMap Oracle docs, ConcurrentHashMa
Read more