How HashSet works internally in Java ??

Points To Remember

• HashSet returns unordered and unsorted values.
• HashSet contains only the unique values.
• HashSet maintains an internal HashMap to provide uniqueness. 

How Set maintains Uniqueness ??

The following program shows how we add new values to a set.

import java.util.Set;
import java.util.HashSet;
class SetImpl{

  public static void main(String args[]){
     
    Set<object> set = new HashSet<object>();
    set.add(100);
    set.add("Java");
    set.add("String");
    set.add("Java");
    set.add("Java");
    System.out.println(set);
  }

}

Output of the program is [100, String, Java]

Now, the question is how does Set maintains  uniqueness. The answer is that Set internally maintains a HashMap. Surprised ?? If you open the implementation of HashSet in the java api you will get the following implementation.

public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable

{
    private transient HashMap map;
    
    // Dummy value to associate with an Object in the backing Map
    
    private static final Object PRESENT = new Object();
    
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    // SOME CODE ,i.e Other methods in Hash Set
    
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
    
    // SOME CODE ,i.e Other methods in Hash Set
}

So, we achieve uniqueness through HashMap, whenever you create an object of HashSet an object of Hashmap is automatically create. You can see internal working of HashMap at this link. Now, whenever we add an object to Hashset by add()  method, the object we pass is hashed and rehashed to find a bucket location. At this bucket location the object be passed is stored as key and a dummy value is passed along with it to the put(key,value) method of HashMap method.

So, when we do set.add(100); , 100 actually becomes the key and a dummy object (new Object())   which is referred by Object reference PRESENT is passed to the map.put(key,value).

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

The method above as in the HashMap implementation, return true if the map.put(key,value) method returns true. This means the value is successfully added to the HashSet otherwise false is returned.

Main point to remember here is that

• put(key,value) return true, if the key is unique and added to the map.
• If the key is duplicate, then the old value of the key is returned.