Java HashSet Internal Working

HashSet internally uses HashMap to store it’s elements. Whenever you create a HashSet object, one HashMap object associated with it is also created. This HashMap object is used to store the elements you enter in the HashSet. The elements you add into HashSet are stored as keys of this HashMap object. The value associated with those keys will be a constant. In this post, we will see Java HashSet internal working with an example.

Every constructor of HashSet class internally creates one HashMap object. You can check this in the source code of HashSet class. Below is the some sample code of the constructors of HashSet class.

private transient HashMap<E,Object> map;
 
//Constructor - 1
 
public HashSet()
{
        map = new HashMap<>();          //Creating internally backing HashMap object
}
 
//Constructor - 2
 
public HashSet(Collection<? extends E> c)
{
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));     //Creating internally backing HashMap object
        addAll(c);
}
 
//Constructor - 3
 
public HashSet(int initialCapacity, float loadFactor)
{
        map = new HashMap<>(initialCapacity, loadFactor);        //Creating internally backing HashMap object
}
 
//Constructor - 4
 
public HashSet(int initialCapacity)
{
        map = new HashMap<>(initialCapacity);          //Creating internally backing HashMap object
}

You can notice that each and every constructor internally creates one new HashMap object.

Java HashSet Internal Working :

Whenever you insert an element into HashSet using add() method, it actually creates an entry in the internally backing HashMap object with element you have specified as it’s key and constant called “PRESENT” as it’s value. This “PRESENT” is defined in the HashSet class as below.

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

Let’s have a look at add() method of HashSet class.

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

You can notice that, add() method of HashSet class internally calls put() method of backing HashMap object by passing the element you have specified as a key and constant “PRESENT” as it’s value.

remove() method also works in the same manner.

public boolean remove(Object o)
{
        return map.remove(o)==PRESENT;
}

Let’s see one example of HashSet and how it maintains HashMap internally.

public class HashSetExample
{
    public static void main(String[] args)
    {
        //Creating One HashSet object
 
        HashSet<String> set = new HashSet<String>();
 
        //Adding elements to HashSet
 
        set.add("RED");
 
        set.add("GREEN");
 
        set.add("BLUE");
 
        set.add("PINK");
 
        //Removing "RED" from HashSet
 
        set.remove("RED");
    }
}

See the below picture how above program works internally. You can observe that internal HashMap object contains elements of HashSet as keys and constant “PRESENT” as their value.

How HashSet Works Internally In Java

In the same manner, all methods of HashSet class process internally backing HashMap object to get the desired result. If you know how HashMap works, it will be easy for you to understand how HashSet works. You go through the source code of HashSet class once, you will get a clear picture about how HashSet works internally in Java.

Also Read :

Related Posts

22 Comments

  9. Hi,
    Thanks for the above article.
    Can you please provide the Internal Process of HashMap and HashTable concepts?

    Thanks!!!

  10. Hi
    Nice explanation .
    here i didn’t understand properly
    return map.put(e, PRESENT)==null;
    return map.remove(o)==PRESENT;
    above two lines returns true or false how it is ? could u please explain it.

    • The put(K key, V value) method of HashMap returns the previous value associated with this key. If this key wasn’t already present in the Hashmap i.e., the given key had no mapping associated with it previously, then it returns null.
      Hence, return map.put(e, PRESENT)==null —> means that the add method will return true if an element is added to the HashSet, provided the element wasn’t already present in the HashSet ( In such duplicate insertion it will return false).

      Same case applies for — > return map.remove(o)==PRESENT;

    • This is the basic functionality of HashMap when you add any element in HashMap its return the current value associated with that key (key value you want to add) and the replace it will the new one. by default all the values in the HashMap bucket are Null.
      in the below code.
      map.put(e, PRESENT)==null;
      We are trying to add key e with new PRESENT value. If this is first time (means there is no value associated with key e) there is null as current value so it will return that. Now here we are checking if the value is not there then map.put(e, PRESENT) will return null and map.put(e, PRESENT)==null become true.
      In other hand it e already has value, then map.put(e, PRESENT)==null will be false.
      How this will helpful

  12. For HashSet hash is calculated using the value itself as there is no key, value pair to be added in HashSet. In HashSet we have add(E e) method which takes just the element to be added as parameter.

  13. SIr, is hashSet is a class or a method in java? because from above diagram it clearly seen that u have declared HashSet has a method.

  14. i want explanation about when more than one element is added to bucket or at same index and also if duplicate is found at same index.

Leave a Reply