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

HTTP : Must known Protocol (Part 1)

Image
Hypertext Transfer Protocol (HTTP) is an application-level protocol for distributed, collaborative, hypermedia information systems.Basically, HTTP is a TCP/IP based communication protocol, that is used to deliver data (HTML files, image files, query results, etc.) on the World Wide Web.The default port is TCP 80, but other ports can be used as well. It provides a standardized way for computers to communicate with each other. HTTP specification specifies how clients' request data will be constructed and sent to the server, and how the servers respond to these requests. TCP/IP is responsible for breaking up the packets  into small pieces and taking them to the correct place or ip address where they are supposed to reach. Basic Features of HTTP : HTTP is connectionless: The HTTP client, i.e., a browser initiates an HTTP request and after a request is made, the client disconnects from the server and waits for a response. The server processes the request and re-establishes
Read more