Internal implementation of Set / HashSet

We all know that Set implementations store unique elements. Now we will try and understand what makes sure that Set has unique elements.

Observe the class below and see how elements are stored in a set.

Set.add() method returns boolean. It returns true if an element is stored successfully otherwise false.
Line number 23 in above code will print true because String “a” has been stored in set. But line number 24 prints false because “a” element / string was already present in set.

Now look at the HashSet implementation in Java API’s.

Whenever we create HashSet object, internally a new HashMap is created. This hashmap stores element E as key and PRESENT dummy object as value.

Now we should understand what HashMap.add(key, value) method does.

When we make an attempt to put a key-value pair in hashmap, it checks if same key is present or not. If it finds same key, it overrides the new value with the key and add() method returns old value associated with that key. If same key is not present in map, new entry is made in map and add() method returns null.

So when an attempt is made to add element in set, internally map.put(e, PRESENT)==null; determines whether to return true or false.

Finally to conclude, HashSet uses HashMap internally to store unique elements.

About these ads

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s