HashSet is a class in Java that implements the Set interface and is backed by a hash table, which is actually a HashMap instance. It is a popular data structure in Java as it offers constant time performance for basic operations such as add, remove, contains, and size. However, it does not guarantee the constant order of elements over time. This means that the class does not guarantee the iteration order of the set. The HashSet class allows the null element, and the class also implements the Serializable and Cloneable interfaces.
Important Features of HashSet
HashSet implements the Set Interface.
The underlying data structure for HashSet is a hashtable.
Duplicate values are not allowed in HashSet.
Objects that you insert in HashSet are not guaranteed to be inserted in the same order. Objects are inserted based on their hash code.
NULL elements are allowed in HashSet.
Working of add(), contains(), and iterator() function in HashSet
Below is an example of how to use the add(), contains(), and iterator() functions in HashSet:
import java.util.*;
class Test {
public static void main(String[] args) {
HashSet<String> h = new HashSet<String>();
// Adding keys into HashSet using add()
h.add("gfg");
h.add("courses");
h.add("ide");
// Displaying the HashSet
System.out.println(h);
// Checks for key "ide"
System.out.println(h.contains("ide"));
// Iterating over HashSet
Iterator<String> i = h.iterator();
while (i.hasNext())
System.out.println(i.next() + " ");
}
}
Output:
[courses, gfg, ide]
true
courses
gfg
ide
Methods Description
add(): Used to add the specified element if it is not already present. If the element is already present, then skip and return false.
contains(): Used to return true if an element is present in the set.
iterator(): Used to return an iterator over the elements in the set.
Note that HashSet follows a random order of traversal.
Working of remove(), size(), and isEmpty() function in HashSet
Below is an example of how to use the remove(), size(), and isEmpty() functions in HashSet:
import java.util.*;
class Test {
public static void main(String[] args) {
HashSet<String> h = new HashSet<String>();
// Adding keys into HashSet using add()
h.add("gfg");
h.add("courses");
h.add("ide");
// Displaying the size of HashSet
System.out.println(h.size());
// Removing the key "ide"
h.remove("ide");
// Displaying the size of HashSet
System.out.println(h.size());
// Using for-each loop to traverse
for(String s:h)
System.out.print(s + " ");
// Checking whether the set is empty or not
System.out.println(h.isEmpty());
}
}
Output:
3
2
courses gfg
false
Methods Description
size(): Used to return the number of elements in the HashSet.
remove(): Used to remove the specified element from the HashSet.
isEmpty(): Used to check whether the HashSet is empty or not.
clear(): Used to remove all the elements from the HashSet.
Note that a size can also be defined for better optimization.
Time Complexity
The underlying data structure for HashSet is a hashtable. So, the amortized time complexity for add(), remove(), and contains() method operation of HashSet takes O(1) time, assuming the hash function is well-distributed and there are no collisions. This means that adding, removing, and checking for the presence of an element in a HashSet takes constant time on average, regardless of the size of the HashSet. However, in the worst case, where all the elements end up in the same bucket due to collisions, the time complexity of these operations can degrade to O(n), where n is the size of the HashSet.
The size() and isEmpty() methods of HashSet also take constant time, O(1), in the worst case. However, iterating over a HashSet using its iterator() method takes time proportional to the size of the HashSet, O(n), where n is the number of elements in the HashSet.
It is important to note that the iteration order of elements in a HashSet is undefined and may change over time due to rehashing. This means that you cannot rely on the order of elements in a HashSet, and if you need to maintain a specific order, you should use a different data structure, such as a TreeSet.
In conclusion, HashSet is a very efficient data structure for storing a collection of unique elements in Java, and it provides constant time performance for the basic operations of adding, removing, and checking for the presence of an element. However, you should be aware of its limitations, such as the lack of ordering guarantees and the potential worst-case performance of O(n) due to collisions.