Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to Java HashSet — internal working backed by HashMap, hashing mechanism, duplicate detection, equals/hashCode contract, performance analysis, and practical examples.
What is HashSet?
java.util.HashSet is the most commonly used implementation of the Set interface. It stores unique elements (no duplicates) with no ordering guarantee, providing O(1) average performance for add, remove, and contains operations.
java example
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, SerializableKey characteristics:
- No duplicate elements — uniqueness determined by
equals()andhashCode() - No ordering guarantee — iteration order is unpredictable
- Allows one null element
- Not synchronized
- O(1) average for add/remove/contains
How Duplicate Detection Works
When you call set.add(element):
- Compute
element.hashCode() - Find the bucket:
index = hash & (capacity - 1) - Walk the bucket chain:
- If any existing key has same hash AND
equals()returns true → element already exists → returnfalse - If no match → add new entry → return
true
java example
HashSet<String> set = new HashSet<>();
set.add("Hello"); // hashCode = 69609650, bucket = X → added (returns true)
set.add("World"); // hashCode = 83766130, bucket = Y → added (returns true)
set.add("Hello"); // hashCode = 69609650, bucket = X → found existing! (returns false)The equals() and hashCode() Contract
For HashSet to work correctly with custom objects:
Example
public class Student {
private int id;
private String name;
// MUST override both equals() AND hashCode()
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id == student.id && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name);
}
}
Without proper equals/hashCode:
java example
Set<Student> students = new HashSet<>();
students.add(new Student(1, "Alice"));
students.add(new Student(1, "Alice")); // SHOULD be duplicate...
// Without overrides: size = 2 (BAD — treated as different objects!)
// With proper overrides: size = 1 (CORRECT — detected as duplicate)Time Complexity
| Operation | Average | Worst Case |
|---|---|---|
| ----------- | :-: | :-: |
add(E e) | O(1) | O(log n)* |
remove(Object o) | O(1) | O(log n)* |
contains(Object o) | O(1) | O(log n)* |
size() | O(1) | O(1) |
isEmpty() | O(1) | O(1) |
| Iteration | O(capacity + n) | O(capacity + n) |
*Worst case with Java 8+ treeification (inherited from HashMap). Without it, worst case is O(n).
Complete Example
java example
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<String> fruits = new HashSet<>();
// Adding elements
System.out.println(fruits.add("Apple")); // true (added)
System.out.println(fruits.add("Banana")); // true (added)
System.out.println(fruits.add("Cherry")); // true (added)
System.out.println(fruits.add("Apple")); // false (duplicate!)
System.out.println(fruits.add(null)); // true (null allowed)
System.out.println("Set: " + fruits);
System.out.println("Size: " + fruits.size()); // 4
// Checking membership
System.out.println("Contains Apple? " + fruits.contains("Apple")); // true
System.out.println("Contains Mango? " + fruits.contains("Mango")); // false
// Removing
fruits.remove("Banana");
fruits.remove("NotExist"); // No error — just returns false
// Bulk operations
Set<String> moreFruits = new HashSet<>(Arrays.asList("Date", "Apple", "Fig"));
// Union
Set<String> union = new HashSet<>(fruits);
union.addAll(moreFruits);
System.out.println("Union: " + union);
// Intersection
Set<String> intersection = new HashSet<>(fruits);
intersection.retainAll(moreFruits);
System.out.println("Intersection: " + intersection);
// Difference
Set<String> difference = new HashSet<>(fruits);
difference.removeAll(moreFruits);
System.out.println("Difference: " + difference);
// Iteration (no guaranteed order!)
for (String fruit : fruits) {
System.out.println(" " + fruit);
}
// Java 8+ operations
fruits.removeIf(f -> f != null && f.startsWith("C"));
fruits.forEach(System.out::println);
}
}Output
Set: [Apple, Mango, Banana, Cherry] Duplicate added? false Size: 4 Contains Mango: true After remove Banana: [Apple, Mango, Cherry]
Constructors and Capacity
java example
// Default: capacity 16, load factor 0.75
Set<String> set1 = new HashSet<>();
// Custom initial capacity
Set<String> set2 = new HashSet<>(100);
// Custom capacity and load factor
Set<String> set3 = new HashSet<>(100, 0.9f);
// From another collection (removes duplicates!)
List<String> listWithDupes = Arrays.asList("A", "B", "A", "C", "B");
Set<String> set4 = new HashSet<>(listWithDupes); // {A, B, C}
// Pre-sizing tip: for N expected elements
int capacity = (int) (expectedSize / 0.75f) + 1;
Set<String> optimized = new HashSet<>(capacity);Common Patterns
Remove Duplicates from a List
Example
List<Integer> withDuplicates = Arrays.asList(1, 3, 2, 1, 4, 3, 2, 5);
// Removes duplicates (loses order)
Set<Integer> unique = new HashSet<>(withDuplicates);
// {1, 2, 3, 4, 5} — order not guaranteed
// Removes duplicates (preserves order)
Set<Integer> preserveOrder = new LinkedHashSet<>(withDuplicates);
// [1, 3, 2, 4, 5] — first occurrence order
Check for Duplicates
java example
public static <T> boolean hasDuplicates(List<T> list) {
return list.size() != new HashSet<>(list).size();
}Find Common Elements
Example
public static <T> Set<T> findCommon(Collection<T>... collections) {
Set<T> result = new HashSet<>(collections[0]);
for (int i = 1; i < collections.length; i++) {
result.retainAll(collections[i]);
}
return result;
}
Count Unique Elements
java example
long uniqueCount = list.stream().distinct().count();
// OR
int uniqueCount = new HashSet<>(list).size();Set Operations (Mathematical)
java example
Set<Integer> A = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> B = new HashSet<>(Arrays.asList(3, 4, 5, 6, 7));
// Union: A ∪ B
Set<Integer> union = new HashSet<>(A);
union.addAll(B); // {1, 2, 3, 4, 5, 6, 7}
// Intersection: A ∩ B
Set<Integer> intersection = new HashSet<>(A);
intersection.retainAll(B); // {3, 4, 5}
// Difference: A - B
Set<Integer> difference = new HashSet<>(A);
difference.removeAll(B); // {1, 2}
// Symmetric Difference: A △ B (in either but not both)
Set<Integer> symDiff = new HashSet<>(union);
symDiff.removeAll(intersection); // {1, 2, 6, 7}
// Subset check
Set<Integer> C = new HashSet<>(Arrays.asList(2, 3));
boolean isSubset = A.containsAll(C); // true — C ⊆ A
// Disjoint check (no common elements)
boolean disjoint = Collections.disjoint(A, B); // falseHashSet vs TreeSet vs LinkedHashSet
| Feature | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| Ordering | None | Insertion order | Sorted |
| add/remove/contains | O(1) | O(1) | O(log n) |
| Backed by | HashMap | LinkedHashMap | TreeMap |
| Null elements | One null | One null | ❌ None |
| Memory | Lowest | Medium | Highest |
| Best for | Fast lookup | Order + fast lookup | Sorted iteration |
| Iterator | Unpredictable | Insertion order | Ascending sort order |
Thread Safety
HashSet is NOT thread-safe:
java example
// Option 1: Synchronized wrapper
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
// Must still synchronize during iteration:
synchronized (syncSet) {
for (String s : syncSet) { ... }
}
// Option 2: CopyOnWriteArraySet (read-heavy workloads)
Set<String> cowSet = new CopyOnWriteArraySet<>();
// Option 3: ConcurrentHashMap.newKeySet() (Java 8+)
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();Common Mistakes
1. Not Overriding hashCode() with equals()
java example
// BROKEN — objects "equal" by equals() but different hashCode
class Point {
int x, y;
@Override public boolean equals(Object o) {
Point p = (Point) o;
return x == p.x && y == p.y;
}
// Missing hashCode()! HashSet won't detect duplicates!
}
Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
points.add(new Point(1, 2)); // Added as "new" — size is 2!2. Mutable Elements
java example
Set<List<String>> set = new HashSet<>();
List<String> list = new ArrayList<>(Arrays.asList("A", "B"));
set.add(list);
System.out.println(set.contains(list)); // true
list.add("C"); // Mutate the element — hashCode changes!
System.out.println(set.contains(list)); // false! Lost in wrong bucket!
set.remove(list); // false! Can't find it to remove!
// Memory leak — element is stuck in the set but unreachable!3. Relying on Iteration Order
java example
// WRONG — HashSet order is unpredictable
Set<String> set = new HashSet<>(Arrays.asList("B", "A", "C"));
String first = set.iterator().next(); // Could be A, B, or C!
// If you need order, use LinkedHashSet or TreeSet4. Using == Instead of contains()
java example
// WRONG
if (set == element) { ... } // Compares reference to the Set object!
// CORRECT
if (set.contains(element)) { ... }Interview Questions
Q1: How does HashSet work internally?
A: HashSet is backed by a HashMap. Elements are stored as keys in the HashMap, with a shared dummy Object as the value. Duplicate detection uses hashCode() for bucket placement and equals() for comparison.
Q2: Why does HashSet not allow duplicates?
A: Because it uses HashMap's key uniqueness guarantee. When you add an element, HashMap checks if the key already exists (same hash + equals). If so, put() returns the old value (not null), and HashSet.add() returns false.
Q3: Can HashSet contain null?
A: Yes, exactly one null element. Null has a hash of 0 and goes to bucket 0.
Q4: What happens if you don't override hashCode() but override equals()?
A: Two logically equal objects may have different hashCodes, placing them in different buckets. HashSet won't detect them as duplicates — both will be stored.
Q5: What is the time complexity of HashSet operations?
A: Average O(1) for add, remove, contains. Worst case O(log n) with Java 8+ treeification (or O(n) without).
Q6: How would you make a thread-safe Set?
A: Use Collections.synchronizedSet(new HashSet<>()), CopyOnWriteArraySet, or ConcurrentHashMap.newKeySet().
Q7: What is the difference between HashSet and HashMap?
A: HashSet stores only keys (unique elements). HashMap stores key-value pairs. Internally, HashSet uses HashMap with a dummy value.
Q8: How does HashSet detect duplicates internally?
A: When you call add(element), HashSet delegates to its internal HashMap's put(element, PRESENT). HashMap uses hashCode() to find the bucket, then equals() to check if an identical key already exists. If a match is found, the element is considered duplicate and not added.
Q9: What is the relationship between hashCode() and equals() in HashSet?
A: If two objects are equal per equals(), they MUST have the same hashCode(). If hashCode() differs, HashSet won't even check equals() (different bucket). If hashCode() is same but equals() returns false, both objects coexist in the same bucket (collision). Violating the hashCode-equals contract leads to duplicate entries in HashSet.
Q10: Why doesn't HashSet guarantee iteration order?
A: HashSet is backed by a HashMap, which distributes elements across buckets based on hash values. Iteration traverses buckets sequentially (0, 1, 2, ...). Element placement depends on hashCode, capacity, and load — adding/removing elements or resizing can completely change which bucket an element lands in.
Q11: Can you store null in a HashSet?
A: Yes, exactly one null element is allowed. Internally, HashMap handles null key specially — it always goes to bucket 0. Since HashSet uses HashMap with element as key, one null can be stored. TreeSet does NOT allow null (throws NullPointerException during comparison).
Q12: How do you create a synchronized HashSet?
A: Use Collections.synchronizedSet(new HashSet<>()) for a synchronized wrapper, or ConcurrentHashMap.newKeySet() (Java 8+) for a concurrent set backed by ConcurrentHashMap. The latter provides better performance under contention since it uses fine-grained locking.
Summary
| Aspect | HashSet |
|---|---|
| Backed by | HashMap |
| Duplicates | Not allowed |
| Ordering | None guaranteed |
| Null | One null allowed |
| Performance | O(1) average |
| Key requirement | Proper equals() AND hashCode() |
| Thread-safe | No |
| Best for | Fast uniqueness checks, set operations |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for HashSet in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, collections, framework, set
Related Java Master Course Topics
Continue learning this concept
Collections FrameworkLinkedHashSet in JavaComplete guide to Java LinkedHashSet — insertion-order preservation, internal working backed by LinkedHashMap, comparison with HashSet and TreeSet, and practical use cases.Collections FrameworkTreeSet in JavaComplete guide to Java TreeSet — Red-Black tree implementation, NavigableSet operations, natural and custom ordering, range queries, ceiling/floor methods, and practical examples.Collections FrameworkCollections Framework OverviewComplete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.Collections FrameworkCollections Practice ProgramsComprehensive Java Collections practice programs covering List, Set, Map, Queue operations with solutions, explanations, and time complexity analysis.Collections FrameworkComparable vs Comparator in JavaDeep dive into Comparable and Comparator interfaces in Java — natural ordering, custom sorting, lambda expressions, method references, and practical comparisons with examples.Collections FrameworkGenerics in JavaComplete guide to Java Generics — type parameters, bounded types, wildcards, type erasure, generic methods, generic classes, and common patterns with practical examples.