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