Internal Working of Hashset in Java

HashSet and HashMap design

What Is HashSet?

HashSet is one of the data structures in the Java Collections framework.

Let’s see the important points:

1. It stores unique elements and permits null
2. Do not allows duplicates
3. It is backed by a HashMap
4. It doesn’t maintain insertion order
5. It is not thread-safe

How HashSet Object Is Created and Initialized?

Whenever we create an instance of HashSet it internally creates an instance of HashMap, basically, each HashSet is backed by a HashMap internally. Let’s see the code block to understand this:

HashSet Object Creation:

1	Set<String> colorSet = new HashSet<String>();

HashSet Constructor:

1	private transient HashMap<E,Object> map;
2
3	// Dummy value to associate with an Object in the backing Map
4	private static final Object PRESENT = new Object();
5
6	/**
7	* Constructs a new, empty set; the backing HashMap instance has
8	* default initial capacity (16) and load factor (0.75).
9	*/
10	public HashSet() {
11	map = new HashMap<>();
12	}

Every HashSet object has a map field of type HashMap. This reference variable gets initialized when the HashSet() constructor is called at the time of the creation of the HashSet object.

Note that HashMap stores the entries in key-value pairs but HashSet is a set of unique elements. Hence the HashSet entries are made key-value pairs using a dummy Object called PRESENT.

Initial capacity of HashSet is 16 and the load factor of 0.75.

How the Elements Are Added to HashSet?

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

Adding an element to set

The add method adds the specified element to this set if it is not already present in the backup map. If this set already contains the element, the method call leaves the set unchanged, and add method returns false. Otherwise, it returns true when added successfully.

How To Remove an Element From HashSet?

1	public boolean remove(Object o) {
2	return map.remove(o)==PRESENT;
3	}

Remove an element from the set

The call to remove(Object o) removes the specified element from the set if it is present and returns true otherwise returns false.

Now Let’s See a Few Other Important Methods of the HashSet Class:

• iterator() returns an iterator over the elements in this set and the element returned are in no particular order.

1	public Iterator<E> iterator() {
2	return map.keySet().iterator();
3	}

return an Iterator for the elements in this set

• size()returns the number of elements present in this set.

1	public int size() {
2	return map.size();
3	}

return the number of elements in this set

• isEmpty() returns true if this set contains no elements.

1	public boolean isEmpty() {
2	return map.isEmpty();
3	}

check if the set is empty or not

• contains(Object o) returns true if this set contains the specified element.

1	public boolean contains(Object o) {
2	return map.containsKey(o);
3	}

check if the element is present or not

• clear() removes all the elements of this set and the set will be empty after this method call.

1	public void clear() {
2	map.clear();
3	}

clear the set

• Refer to the image below to get a complete idea of how the set and map are constructed.

HashSet and HashMap design