As we all know, a collection is a clearly defined collection of different objects. Each member of the set is called an element of the set. So in other words, we can say that a set will never contain duplicate elements. But how to implement HashSet, LinkedHashSet, TreeSet and other classes in the Java Set interface to achieve this uniqueness. In this article, we will discuss the truth behind this uniqueness.

We will understand this with an example.Let us see the output of the following program which try to add duplicate elements in a HashSet.

// Java program to demonstrate
// internal working of HashSet

import java.util.HashSet;

class Test
{	
	public static void main(String args[])
	{
		// creating a HashSet
		HashSet hs = new HashSet();
		
		// adding elements to hashset
		// using add() method
		boolean b1 = hs.add("Geeks");
		boolean b2 = hs.add("GeeksforGeeks");
		
		// adding duplicate element
		boolean b3 = hs.add("Geeks");
		
		// printing b1, b2, b3
		System.out.println("b1 = "+b1);
		System.out.println("b2 = "+b2);
		System.out.println("b3 = "+b3);
		
		// printing all elements of hashset
		System.out.println(hs);
			
	}
}

Output:

b1 = true
b2 = true
b3 = false
[GeeksforGeeks, Geeks]

Now it is clear from the output that when we try to add a duplicate element to the collection using the add() method, it returns false and the element will not be added to the hashset because it already exists. Now the question is, how does the add() method check whether the collection already contains the specified element. If we take a closer look at the add() method and default constructor in the HashSet class, it will be more clear.

// predefined HashSet class
public class HashSet
{
    // A HashMap object 
    private transient HashMap map;

    // A Dummy value(PRESENT) to associate with an Object in the Map
    private static final Object PRESENT = new Object();
    
    // default constructor of HashSet class
    // It creates a HashMap by calling 
    // default constructor of HashMap class
    public HashSet() {
        map = new HashMap<>();
    }

    // add method 
    // it calls put() method on map object
    // and then compares it's return value with null
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
 
    // Other methods in Hash Set
}

Now you can see that whenever we create a HashSet, it will create a HashMap internally. If we use the add() method to insert an element into this HashSet, it will actually be called on the internally created HashMap object The put() method and its key and constant object using the element you specify is called "PRESENT" because of its value. So we can say that Set has achieved uniqueness through HashMap. Now the whole story revolves around how the HashMap and put() methods work internally.

As we know that each key in HashMap is unique, when we call the put(Key, Value) method, it returns the previous value associated with the key, or null if there is no key mapping. So in the add() method, we check whether the return value of the map.put(key, value) method is null.

1. If map.put(key, value) returns null, the statement "map.put(e, PRESENT) == null" will return true and add the element to the HashSet (internal HashMap).
2. If map.put(key, value) returns the old value of the key, the statement "map.put(e, PRESENT) == null" will return false and the element will not be added to the HashSet (internal HashMap).

Because LinkedHashSet extends HashSet, it internally calls the HashSet constructor with super(). Likewise, when a TreeSet object is created internally, a navigation map object is created as a maintenance map.