HashSet
Imagine a system that stores registered email addresses. If the same email address is submitted twice, the application should not create two identical registrations. You need a collection that naturally focuses on uniqueness rather than position.
That is exactly where HashSet becomes useful. HashSet is a Set implementation that stores unique elements and uses hashing to provide efficient average-case operations.
Core Idea: HashSet is designed for storing a group of unique elements where fast membership checking is more important than maintaining insertion or sorted order.
Why Does HashSet Exist?
Suppose you are collecting the skills possessed by employees:
Java Spring SQL Java Docker Spring
If your goal is simply to know which skills exist, duplicates add no useful information. A Set removes that duplication naturally.
Set<String> skills = new HashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
skills.add("Java");
skills.add("Docker");
skills.add("Spring");
System.out.println(skills);
The duplicate Java and Spring values are not stored as separate elements.
Simple analogy: Think of HashSet like a guest list where each person can appear only once. If someone tries to register again, the collection simply keeps the existing membership.
HashSet Hierarchy
HashSet implements the Set interface, which extends Collection.
Collection
|
+-- Set
|
+-- HashSet
This means HashSet follows the Set contract: duplicate elements are not permitted.
Creating a HashSet
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Set<String> languages = new HashSet<>();
languages.add("Java");
languages.add("C#");
languages.add("Python");
System.out.println(languages);
}
}
The variable is declared using the Set interface and instantiated using HashSet. This is usually a good approach because the code depends on the abstraction rather than unnecessarily exposing implementation details.
Adding Elements
The add() method inserts an element into the HashSet.
Set<String> languages = new HashSet<>();
languages.add("Java");
languages.add("Spring");
languages.add("SQL");
System.out.println(languages);
The add() method returns a boolean indicating whether the Set changed as a result of the operation.
Set<String> languages = new HashSet<>();
boolean first = languages.add("Java");
boolean second = languages.add("Java");
System.out.println(first);
System.out.println(second);
The first call returns true because Java was newly added. The second returns false because an equal element is already present.
Useful Detail: The boolean return value of add() is an easy way to determine whether an element was actually inserted.
Duplicate Elements
The defining property of HashSet is that it does not store duplicate elements according to the Set's equality rules.
Set<Integer> numbers = new HashSet<>(); numbers.add(10); numbers.add(20); numbers.add(10); numbers.add(30); numbers.add(20); System.out.println(numbers);
Only one occurrence of each distinct value remains.
Does HashSet Maintain Insertion Order?
No. HashSet does not guarantee insertion order.
Set<String> names = new HashSet<>();
names.add("Bibhu");
names.add("Rahul");
names.add("Priya");
for (String name : names) {
System.out.println(name);
}
The iteration order should not be treated as the order in which elements were inserted.
Important: Never write application logic that depends on the apparent iteration order of a HashSet. If insertion order matters, consider LinkedHashSet. If sorted order matters, consider TreeSet.
How HashSet Works Internally
The name HashSet gives you an important clue: hashing is central to how it works.
Conceptually, when an element is added, Java uses the element's hashCode() to help determine where the element should be stored. When searching for an element, the hash value helps narrow down where Java needs to look.
Element | v hashCode() | v Hash-based location | v Compare candidates using equals()
This is why correctly implementing equals() and hashCode() is critical when custom objects are stored in HashSet.
hashCode() and equals()
Two rules are especially important:
- If two objects have the same hashCode(), they do not necessarily have to be equal.
The second point is important because different objects can produce the same hash value. This is called a hash collision.
Golden Rule: Equal objects must have equal hash codes. Breaking this contract can cause HashSet and HashMap to behave incorrectly.
Hash Collision
A hash collision occurs when different objects produce the same hash code.
Object A
|
+-- hashCode() = 100
\
\
Object B +-- Same hash value
|
+-- hashCode() = 100
A collision does not automatically mean the Set considers the objects duplicates. Java can use equality comparison to distinguish objects that share the same hash code.
The important lesson is that hashCode() helps locate candidates, while equals() determines equality.
Example with a Custom Class
Suppose you create an Employee class and want two Employee objects with the same employee ID to be considered equal.
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Employee)) {
return false;
}
Employee other = (Employee) obj;
return id == other.id;
}
@Override
public int hashCode() {
return Integer.hashCode(id);
}
}
Now HashSet can correctly identify Employee objects with the same ID as equal.
Set<Employee> employees = new HashSet<>(); employees.add(new Employee(101, "Bibhu")); employees.add(new Employee(101, "Bibhu")); System.out.println(employees.size());
The result is 1 because the two objects have equal IDs, and their equals() and hashCode() implementations agree.
Practical Lesson: When using custom objects in HashSet, always think about what "duplicate" should mean in your domain and implement equals()/hashCode() accordingly.
Checking Whether an Element Exists
The contains() method checks whether an equal element exists in the Set.
Set<String> skills = new HashSet<>();
skills.add("Java");
skills.add("Spring");
if (skills.contains("Java")) {
System.out.println("Java is available");
}
HashSet is particularly useful when membership checks are common because hashing provides efficient average-case lookup.
Removing Elements
The remove() method removes an element if an equal element is present.
Set<String> skills = new HashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
skills.remove("Spring");
System.out.println(skills);
The remove() method returns true if the Set actually changed.
Checking Size and Empty State
Set<String> skills = new HashSet<>();
skills.add("Java");
skills.add("Spring");
System.out.println(skills.size());
System.out.println(skills.isEmpty());
size() returns the number of unique elements currently stored, while isEmpty() tells you whether there are no elements.
Iterating Through HashSet
The enhanced for loop is commonly used to process HashSet elements.
Set<String> skills = new HashSet<>();
skills.add("Java");
skills.add("Spring");
skills.add("SQL");
for (String skill : skills) {
System.out.println(skill);
}
Remember that the iteration order is unspecified. The loop is guaranteed to visit the elements, but not in a business-defined order.
Using Iterator
Iterator<String> iterator = skills.iterator();
while (iterator.hasNext()) {
String skill = iterator.next();
System.out.println(skill);
}
If you need to remove the current element safely while iterating, use the Iterator's remove() method.
Iterator<String> iterator = skills.iterator();
while (iterator.hasNext()) {
String skill = iterator.next();
if (skill.equals("SQL")) {
iterator.remove();
}
}
HashSet and Null
HashSet permits a single null element.
Set<String> values = new HashSet<>();
values.add("Java");
values.add(null);
values.add(null);
System.out.println(values);
Only one null element can exist because a Set does not contain duplicates.
Remember: HashSet can contain at most one null element.
HashSet Performance
For a properly distributed hash function, HashSet provides efficient average-case performance for its fundamental operations.
| Operation | Average-Case Complexity | Purpose |
|---|---|---|
| add() | O(1) | Add an element if it is not already present. |
| contains() | O(1) | Check whether an element exists. |
| remove() | O(1) | Remove an element if present. |
| size() | O(1) | Return the number of stored elements. |
| Iteration | O(n) plus table-related overhead | Visit all elements. |
These are average-case expectations. Hashing performance depends on factors such as hash distribution, collisions, table state, and implementation details.
Initial Capacity and Load Factor
HashSet is backed by a hash table, and two concepts are useful when discussing its internal behavior: capacity and load factor.
Capacity represents the size of the underlying hash-table structure, while load factor controls how full the table can become before resizing occurs.
Set<String> names =
new HashSet<>(100, 0.75f);
This constructor specifies an initial capacity and load factor. The exact resizing behavior is an implementation detail, but the general goal is to maintain a balance between memory usage and efficient lookup.
Important: Capacity is not the number of elements in the Set. The Set's size() reports the number of actual elements.
HashSet vs ArrayList
Both collections can store multiple objects, but they solve different problems.
| Feature | HashSet | ArrayList |
|---|---|---|
| Interface | Set | List |
| Duplicates | Not allowed | Allowed |
| Ordering | No guaranteed insertion order | Maintains insertion order |
| Index access | Not supported | Supported |
| Average membership check | O(1) | O(n) |
| Typical purpose | Unique elements and fast membership checks | Ordered elements and positional access |
HashSet vs LinkedHashSet vs TreeSet
The three most important general-purpose Set implementations differ mainly in ordering and performance characteristics.
| Feature | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| Duplicates | Not allowed | Not allowed | Not allowed |
| Insertion order | Not guaranteed | Maintained | Not the purpose |
| Sorted order | No | No | Yes |
| Typical basic operation | O(1) average | O(1) average | O(log n) |
| Best use | Unique elements and fast lookup | Unique elements with predictable insertion order | Unique elements in sorted order |
HashSet with Custom Objects
When storing custom objects, duplicate detection depends on the object's equality contract.
class Product {
private int id;
public Product(int id) {
this.id = id;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Product)) {
return false;
}
Product other = (Product) obj;
return id == other.id;
}
@Override
public int hashCode() {
return Integer.hashCode(id);
}
}
Now two Product objects with the same ID can be recognized as equal by HashSet.
Set<Product> products = new HashSet<>(); products.add(new Product(101)); products.add(new Product(101)); System.out.println(products.size());
The size is 1 because the objects represent the same logical product according to equals() and hashCode().
Mutable Objects as HashSet Elements
There is a subtle but important danger when mutable objects are used as Set elements. If fields involved in equals() or hashCode() are changed after insertion, the object may no longer behave correctly inside the hash table.
class Employee {
private int id;
public Employee(int id) {
this.id = id;
}
public void setId(int id) {
this.id = id;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Employee)) {
return false;
}
Employee other = (Employee) obj;
return id == other.id;
}
@Override
public int hashCode() {
return Integer.hashCode(id);
}
}
If an Employee is inserted into a HashSet and its ID is later changed, the hash-based location associated with the original state may no longer match the object's new hash code.
Best Practice: Avoid mutating fields that participate in equals() and hashCode() while an object is being used as a HashSet element. Immutable keys and values are often safer.
Removing Duplicates from a List
A common practical use of HashSet is removing duplicate values from a List.
List<String> languages = new ArrayList<>();
languages.add("Java");
languages.add("Spring");
languages.add("Java");
languages.add("SQL");
languages.add("Spring");
Set<String> uniqueLanguages =
new HashSet<>(languages);
System.out.println(uniqueLanguages);
This removes duplicates, but remember that HashSet does not preserve the original insertion order.
If preserving insertion order is required, use a LinkedHashSet instead.
Set<String> uniqueLanguages =
new LinkedHashSet<>(languages);
System.out.println(uniqueLanguages);
HashSet and Set Operations
Sets are especially useful for mathematical-style operations such as union, intersection, and difference.
Union
Set<String> backend = new HashSet<>();
backend.add("Java");
backend.add("Spring");
Set<String> database = new HashSet<>();
database.add("SQL");
database.add("MongoDB");
Set<String> allSkills =
new HashSet<>(backend);
allSkills.addAll(database);
System.out.println(allSkills);
The resulting Set contains the unique elements from both Sets.
Intersection
Set<String> teamA =
new HashSet<>();
teamA.add("Java");
teamA.add("SQL");
teamA.add("Docker");
Set<String> teamB =
new HashSet<>();
teamB.add("Java");
teamB.add("Docker");
teamB.add("AWS");
Set<String> common =
new HashSet<>(teamA);
common.retainAll(teamB);
System.out.println(common);
retainAll() keeps only elements that also exist in the other collection.
Difference
Set<String> result =
new HashSet<>(teamA);
result.removeAll(teamB);
System.out.println(result);
removeAll() removes elements that are also present in the supplied collection.
Common Beginner Mistakes
- Expecting insertion order: HashSet does not guarantee insertion-order iteration.
- Expecting duplicates: A Set intentionally rejects duplicate elements according to its equality rules.
- Using custom objects without equals()/hashCode(): Logical duplicates may not be recognized as duplicates.
- Changing hash-relevant fields after insertion: Mutating an object's equality or hash state can make Set operations unreliable.
- Assuming hashCode() alone determines equality: Equal objects need equal hash codes, but equal hash codes do not prove equality.
- Using HashSet when sorted order is required: Use TreeSet when ordered keys are part of the requirement.
- Using HashSet when insertion order matters: Use LinkedHashSet instead.
- Assuming HashSet is thread-safe: HashSet is not inherently synchronized.
Best Practices
- Use HashSet when uniqueness and efficient average-case membership checks are the main requirements.
- Use Set as the reference type when implementation-specific behavior is unnecessary.
- Implement equals() and hashCode() consistently for custom objects stored in HashSet.
- Avoid changing fields involved in equality or hashing while objects are stored in the Set.
- Use LinkedHashSet when insertion order must be preserved.
- Use TreeSet when sorted ordering is required.
- Do not rely on HashSet iteration order in business logic.
Interview Insights
Question: What is HashSet?
Answer: HashSet is a Set implementation that stores unique elements using hash-based storage. It provides efficient average-case add, remove, and contains operations.
Question: Does HashSet maintain insertion order?
Answer: No. HashSet does not guarantee insertion order. LinkedHashSet should be used when insertion-order iteration is required.
Question: How does HashSet identify duplicates?
Answer: Hashing is used to locate candidate elements, and equality comparison is used to determine whether an existing element is equal to the new element.
Question: Why must equals() and hashCode() be consistent?
Answer: Hash-based collections depend on hashCode() for locating candidates and equals() for equality. If equal objects produce different hash codes, the collection can fail to recognize them correctly.
Question: What happens if an object changes after being inserted into HashSet?
Answer: If fields used by equals() or hashCode() change, the object may become difficult or impossible to find correctly because its new hash state may not correspond to its original position.
Question: Can HashSet contain null?
Answer: Yes. HashSet permits a single null element.
Quick Revision
| Concept | Key Point |
|---|---|
| HashSet | Hash-based Set implementation for unique elements. |
| Duplicates | Not allowed according to Set equality rules. |
| Order | No guaranteed insertion order. |
| add() | Returns true when the Set changes and false when an equal element already exists. |
| contains() | Checks whether an equal element exists. |
| remove() | Removes an equal element if present. |
| Null | A single null element is permitted. |
| Average add/contains/remove | Typically O(1), assuming good hash distribution. |
| equals() | Determines logical equality between candidate objects. |
| hashCode() | Helps locate the hash-based storage area. |
| Insertion order required | Prefer LinkedHashSet. |
| Sorted order required | Prefer TreeSet. |
HashSet is much more than a collection that "doesn't allow duplicates." Its real strength comes from combining uniqueness with hash-based lookup. Once you understand the relationship between hashCode(), equals(), collisions, and object mutability, HashSet becomes far easier to use correctly in real applications. In the next chapter, we will explore LinkedHashSet, which keeps the uniqueness of Set while adding predictable insertion-order iteration.