01 logo

How HashSet Works Internally? — Java

Learn working of HashSet in java with a simple guide.

By Rakshit ShahPublished 2 years ago 4 min read
Like
How Hashmap works Internally in java | Image by Author

You may find this frequently asked question in IT industries for Java. Prepare this one on high priority before you appearing in the interview. First of all, find the HashSet in the collection tree from below the given hierarchy.

Collection Interface tree | Image via Edureka

Let’s have a deep dive into HashSet and its internal working in java, prepare this question before you appear for the interview in the IT industry.

Understand What is Set “Interface” first!

A Java Set interface represents a group of elements arranged like an array.

  • It does not allow duplicate elements.
  • When we try to pass the same element that is already available in the Set, then it will not store into the Set.
  • It is used to model the mathematical set abstraction.
  • You can use it when you want data/Elements with unique items

What is HashSet “Class”?

A Java HashSet class represents a set of elements (objects).

  • It does not guarantee the order of elements.
  • It is achieved by storing elements as keys with the same value always.
  • It constructs a collection that uses a hash table for storing elements.
  • It contains unique elements.
  • It inherits the AbstractSet class.
  • It also implements the Set interface.
  • It uses a technique to store elements is called hashing.
  • HashSet uses HashMap internally in Java.
  • [Important Iterator] HashSet does not have any method to retrieve the object from the HashSet. There is only a way to get objects from the HashSet via Iterator.
  • HashSet has default initial capacity = 16.
  • HashSet has default loadfactor = 0.75 or 75%
  • The capacity may increase automatically when more elements to be store.

Understand the syntax for HashSet.

HashSet<String> hs = new HashSet<>();

Here you can see <String> that is the generic type parameter representing the type of element storing in the HashSet.

Observe the right side, new HashSet<>() — keep generic type parameter as blank to achieve polymorphism with any of collection including (List, Set, etc.). If you write syntax as below, then you can’t achieve polymorphism. Instantiation will be limited to MyClassA only. Similarly, you can compare for new HashSet<MyClassA>();

List<MyClass> myList = new LinkedList<MyClassA>();

Anyway, let’s get back to HashSet, HashSet uses a constructor HashSet(int capacity) that represents how many elements can be stored in the HashSet. HashSet uses another constructor HashSet(int capacity, float loadfactor). Here, loadfactor determines the point where the capacity of HashSet would be increased internally.

For example, the product of capacity and loadfactor is 101*0.5=50.5. It means that after storing the 50th element into the HashSet, its capacity will be internally increased to store more elements.

The initial default capacity of HashSet is 16. The default load factor is 0.75.

Gist for Hashset example in java | Image by Author

Output:

Set is [Aabraa, kaaa, Daabra]

Elements using iterator:

Aabraa

kaaa

Daabra

Let’s say if you are adding similar values to your HashSet, it will keep only unique items. From the above example, if you write the same element N times, then:

hs.add("Daabra");

hs.add("Daabra");

It will show “Daabra” only once a time when we iterate and print it in the console. Now you must have a question about How HashSet will ignore the duplicates? When you open the HashSet implementation of the add() method in Java APIs i.e. in rt.jar, You can see the below code.

Gist for Hashset class example - exploring deeply | Image by Author

HashSet call to add(object) is delegated to put(key, value) internally in the HashMap. Where key is the object we have passed and the value is another object, called PRESENT. It is a constant in java.util.HashSet.

We know that each key is unique in the HashMap. So, we pass the argument in the add(E e) method. Here, we need to associate some value to the key. It will associate with Dummy value that is (new Object()) which is referred by Object reference PRESENT.

When we add an element in HashSet like hs.add(“Daabra”), Java does internally is that it will put that element E here “Daabra” as a key into the HashMap (generated during HashSet object creation). It will also put some dummy value that is Object’s object is passed as a value to the key.

Please note below important points about put(key, value):

  1. If the Key is unique and added to the map, then it will return null
  2. If the Key is duplicate, then it will return the old value of the key.
  3. 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.
  4. 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.

Retrieving Object from the HashSet

public Iterator < E > iterator() {

return map.keySet().iterator();

}

We use iterator() method to retrieve object from the HashSet. It is a method of java.util.HashSet class. It returns iterator for backup Map returned by map.keySet().iterator() method.

Reference:

[1] Java book - The Complete Reference by Herbert Schildt

Get my stories in your feeds by subscribing to me, or become a vocal+ member to read all stories of thousands of other writers, participate in all challenges and get a payout with low fees and less payout threshold on Vocal Media.

© Originally published at HashSet Internal Working, also republished on Medium by Author Rakshit Shah(Me).

interview
Like

About the Creator

Rakshit Shah

I am Computer Engineer and love to make websites and software. I am really eager to know about anything. I am curious to read and write cool stuff.

Reader insights

Be the first to share your insights about this piece.

How does it work?

Add your insights

Comments

There are no comments for this story

Be the first to respond and start the conversation.

Sign in to comment

    Find us on social media

    Miscellaneous links

    • Explore
    • Contact
    • Privacy Policy
    • Terms of Use
    • Support

    © 2024 Creatd, Inc. All Rights Reserved.