How does the data storage mechanism work in HashSet and why is hashing used for this task?

HashSet in Java is implemented based on a hash table. When adding an element, HashSet computes its hash code (using the hashCode() method) to determine which "bucket" to place the element in.

If there are already elements in the bucket, a comparison is made using equals() to check for uniqueness — HashSet does not allow duplicates.

Hashing is used to ensure quick access to elements — add, remove, and search operations are performed on average in constant time O(1). This is achieved by distributing elements across buckets based on their hash code, which is much more efficient than, for example, linear search.

Example:

HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple"); // will not be added, as "apple" already exists
System.out.println(set); // [apple, banana]