Java: How HashSet Work?


A Set interface represents a group of unique elements arranged like an array. When we try to pass the duplicate element that is already available in the Set, then it will not store into the Set.

HashSet class

HashSet class implemnets Set interface and extends AbstractSet class.A HashSet class uses Hash Map internally for storing elements by using hashing technique.HashSet store unique elements and does not guarantee the order of elements.

Suppose, you want to create a HashSet to store a group of Strings, then create the HashSet object as:


HashSet hs=new HashSet();  

Where is the generic type parameter to represent HashSet allows only String type objects.

HashSet default constructor create instance of initial capacity 16 and capacity may increase automatically when number of elements reach to load factors. For uniqueness of object generate key as hashcode value. HashSet class doesn’t have method to retrieve object of Instance only way is retrieve object by iteration.

Note: To set your own capacity and loadfactor for HashSet. you can use below constructor.


HashSet hs=new HashSet(int capacity, float loadfactor);  

Here, loadfactor determines when number of elements in HashSet reach to that capacity limit increase capacity internally.the point where the capacity of HashSet would be increased internally.
The initial default capacity of HashSet is 16. The default load factor is 0.75. then 16*0.75=12 when no of elements reach to 12 increase capacity of HashSet to store more elements.

Example HashSet:

import java.util.HashSet;
import java.util.Iterator;

public class HashSetExample1 {
	public static void main(String[] args) {
      HashSet countries=new HashSet();
      countries.add("India");
      countries.add("Pakistan");
      countries.add("China");
      countries.add("Nepal");
      countries.add("Afganistan");
      countries.add("Canada");
      countries.add("Brazil");
      countries.add("Canada");
      countries.add("Brazil");
      countries.add("Thailand");
      countries.add("Malasia");
      countries.add("Russia");
      countries.add("London");
      countries.add("Switzerand");
      //Till that point threshold/capacity value is 12
      System.out.println("Countries Name:"+countries);
      System.out.println("Total Countries:"+countries.size());
      //Duplicate elements not allowed
      System.out.println("Add Dubai:"+countries.add("Dubai"));
      System.out.println("Add Dubai :"+countries.add("Dubai"));//return false when duplicate
      //After adding 13th element Threshold/capacity reach to 24 just double
      System.out.println("Countries Name:"+countries);
      System.out.println("Total Countries:"+countries.size());

     //iteration of Hashset elements
      System.out.println("\n\nPrint Countries by for each:");
      for(String country:countries)
      {
    	 System.out.println(country);
      }

      System.out.println("\n\nPrint Countries by for iterator:");
      Iterator it=countries.iterator();
      while(it.hasNext())
      {
    	  System.out.println(it.next());
      }

	}
}

Output


Countries Name:[Canada, Pakistan, China, Malasia, Brazil, London, Afganistan, Thailand, Nepal, Switzerand, India, Russia]
Total Countries:12
Add Dubai:true
Add Dubai :false
Countries Name:[Malasia, Thailand, Dubai, India, Russia, Canada, Pakistan, China, Brazil, London, Afganistan, Nepal, Switzerand]
Total Countries:13


Print Countries by for each:
Malasia
Thailand
Dubai
India
Russia
Canada
Pakistan
China
Brazil
London
Afganistan
Nepal
Switzerand


Print Countries by for iterator:
Malasia
Thailand
Dubai
India
Russia
Canada
Pakistan
China
Brazil
London
Afganistan
Nepal
Switzerand

In this example we have added duplicate values as Dubai in HashSet. When added it first time by add method return true because Dubai was not in HashSet. When added again return false because it was already added.

How HashSet work?

Now question comes how HashSet, add() method returns true and false. When you will open HashSet implementation of the add() method in Java APIs i.e. rt.jar, you will see the following code in it:

public class HashSet&ltE> extends AbstractSet
{
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();
}
public boolean add(E e)
{
return map.put(e, PRESENT)==null;
}
}

In this HashSet, add(object) methods use HashMap delegated to put(key, value) internally. Where key is the object added on HashSet and value is constant object as PRESENT in java.util.HashSet.

When we create HashSet Object, internally create an object of HashMap. As we know in HashMap each key is unique so, When we call add(E e) method this passing object set as key of HashMap and dummy object (new Object()) which is referred by Object reference PRESENT pass as value.

In HashMap put(key, value):

  • If the Key is unique and added then it will return null
    If the Key is duplicate, then map will return the old value of the key.

Let consider above example, when add country as countries.add(“Dubai”), java internally call HashMap put(“Dubai”,PRESENT) method to add element in map.

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

If the method map.put(key, value) returns null, then the method map.put(e, PRESENT)==null will return true internally, and the element added to the HashSet.
If the method map.put(key, value) returns the old value of the key, then the method map.put(e, PRESENT)==null will return false internally, and the element will not add to the HashSet.

As per given implementation when country “Dubai” added first time put() method return as null because “Dubai” not added before (unique) then add method return true. But when “Dubai” added again put() method will return old object and add method will return false on that case because of duplicate.

Retrieving Object from the HashSet

We use iterator() method of HashSet to retrieve objects. Internally HashSet iterator method called map.keySet().iterator() method.

public Iterator iterator()
{
return map.keySet().iterator();
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s