HashSet and HashMap are hash-based collections designed to provide very fast insertion, deletion, and retrieval operations. Their performance depends on the quality of hash distribution and the number of collisions. In most real-world scenarios, these operations execute in constant time, making them highly efficient for large datasets.
Key Points: • HashSet and HashMap provide O(1) average-time performance for most operations. • Performance depends on hashCode() distribution and collision handling. • Heavy collisions can increase operation time. • Since Java 8, Red-Black Trees improve worst-case performance. • Neither HashSet nor HashMap maintains elements in sorted order.
Time Complexity of HashMap
Insertion (put)
Average Case:
O(1)
Worst Case:
O(n) before Java 8
O(log n) in Java 8+ when a bucket is converted to a Red-Black Tree
Reason:
• HashMap calculates the hash code. • Finds the appropriate bucket. • Inserts the key-value pair.
Retrieval (get)
Average Case:
O(1)
Worst Case:
O(n) before Java 8
O(log n) in Java 8+ after treeification
Reason:
• HashMap directly locates the bucket using hashCode(). • equals() identifies the exact key.
Deletion (remove)
Average Case:
O(1)
Worst Case:
O(n) before Java 8
O(log n) in Java 8+ after treeification
Reason:
• Locate bucket. • Find matching key. • Remove entry.
Time Complexity of HashSet
Since HashSet is internally backed by a HashMap, its performance characteristics are almost identical.
Insertion (add)
Average Case:
O(1)
Worst Case:
O(n) before Java 8
O(log n) in Java 8+ after treeification
Retrieval/Search (contains)
Average Case:
O(1)
Worst Case:
O(n) before Java 8
O(log n) in Java 8+ after treeification
Deletion (remove)
Average Case:
O(1)
Worst Case:
O(n) before Java 8
O(log n) in Java 8+ after treeification
Example: Suppose we store employee IDs in a HashSet.
Code Example:
import java.util.HashSet;
import java.util.Set;
public class Demo {
public static void main(String[] args) {
Set<Integer> employeeIds =
new HashSet<>();
employeeIds.add(101);
employeeIds.add(102);
employeeIds.add(103);
System.out.println(
employeeIds.contains(102));
employeeIds.remove(102);
}
}Output:
true
Why Are Operations Usually O(1)?
Hash-based collections use:
1. hashCode() to determine the bucket. 2. equals() to identify the exact object.
This allows direct access instead of traversing all elements.
Impact of Collisions
No Collision:
Bucket 1 → KeyA
Bucket 2 → KeyB
Bucket 3 → KeyC
Operations remain O(1).
Heavy Collision:
Bucket 1:
KeyA -> KeyB -> KeyC -> KeyD
Search becomes slower because multiple entries must be checked.
Java 8 Improvement:
Bucket 1:
KeyB
/ \KeyA KeyD / KeyC
Red-Black Trees improve lookup performance to O(log n).
Complexity Summary
HashMap:
• put() → O(1) average, O(log n) worst case (Java 8+) • get() → O(1) average, O(log n) worst case (Java 8+) • remove() → O(1) average, O(log n) worst case (Java 8+)
HashSet:
• add() → O(1) average, O(log n) worst case (Java 8+) • contains() → O(1) average, O(log n) worst case (Java 8+) • remove() → O(1) average, O(log n) worst case (Java 8+)
Important Note:
• HashMap stores key-value pairs. • HashSet stores unique elements. • Neither collection guarantees sorted order. • For sorted data, use TreeMap or TreeSet.
Interview Tip: A concise interview answer is:
"HashMap and HashSet provide O(1) average-time complexity for insertion, retrieval, and deletion operations because they use hashing for direct bucket access. In cases of excessive collisions, the worst-case complexity was O(n) before Java 8. From Java 8 onwards, heavily populated buckets are converted into Red-Black Trees, improving the worst-case complexity to O(log n)."