[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":84,"_73":85,"_35":86},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",105,"title","HashSet Internals","slug","java-collections-part-9-hashset-internals","excerpt","Discover how HashSet is backed by HashMap, uniqueness enforcement through hash/equals, iteration order unpredictability, and pitfalls causing 'duplicates' in sets.","# Java Collections Part 9: HashSet - Uniqueness via Hashing\n\nHashSet is Java's primary implementation of a Set - a collection that contains no duplicate elements. But here's the secret: **HashSet is just a HashMap in disguise**. Understanding this relationship unlocks both Set and Map knowledge simultaneously.\n\nThis article explores how HashSet enforces uniqueness, why iteration order is unpredictable, and the common pitfalls that cause \"duplicates\" to appear in what should be unique collections.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Internal Implementation | Backed by `HashMap` |\n| Uniqueness Mechanism | Uses HashMap's key uniqueness |\n| Time Complexity | O(1) average for add/remove/contains |\n| Iteration Order | Undefined (hash-based, not predictable) |\n| Null Elements | Allows one null element |\n| Thread Safety | Not thread-safe |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Explain the HashMap backing**: How HashSet uses HashMap internally\n- **Understand uniqueness**: Why equals() and hashCode() are critical\n- **Perform set operations**: Union, intersection, difference efficiently\n- **Avoid common traps**: Mutable elements, incorrect equals/hashCode\n- **Choose the right Set**: HashSet vs TreeSet vs LinkedHashSet\n\n---\n\n## 🔥 Production Story: The Duplicate Detection Failure\n\nAn e-commerce platform needed to prevent duplicate orders from being processed. The solution seemed simple:\n\n```java\npublic class OrderProcessor {\n private Set processedOrders = new HashSet<>();\n\n public boolean processOrder(Order order) {\n if (processedOrders.contains(order)) {\n log.warn(\"Duplicate order detected: {}\", order.getId());\n return false; // Already processed\n }\n\n processedOrders.add(order);\n submitToPayment(order);\n return true;\n }\n}\n```\n\n**The bug:** Duplicate orders were being processed anyway!\n\n```java\n// ❌ The Order class:\npublic class Order {\n private String orderId;\n private BigDecimal amount;\n private OrderStatus status;\n private Instant createdAt;\n\n // IDE-generated equals() and hashCode() included ALL fields!\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof Order)) return false;\n Order order = (Order) o;\n return Objects.equals(orderId, order.orderId) &&\n Objects.equals(amount, order.amount) &&\n Objects.equals(status, order.status) && // ← Problem!\n Objects.equals(createdAt, order.createdAt);\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(orderId, amount, status, createdAt);\n }\n}\n```\n\n**What happened:**\n\n```java\n// Order comes in:\nOrder order1 = new Order(\"ORD-123\", 99.99, PENDING, now());\nprocessedOrders.add(order1);\n\n// Same order comes again, but status changed:\nOrder order2 = new Order(\"ORD-123\", 99.99, PROCESSING, now());\nprocessedOrders.contains(order2); // false! Different status → different hash!\n\n// \"Duplicate\" gets processed because HashSet doesn't find it\n```\n\n**The fix:**\n\n```java\n// ✅ Only use business identity in equals/hashCode\npublic class Order {\n private final String orderId; // Immutable!\n // ... other fields\n\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof Order)) return false;\n Order order = (Order) o;\n return Objects.equals(orderId, order.orderId); // Only ID\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(orderId); // Only ID\n }\n}\n```\n\n**Lesson:** HashSet uniqueness depends entirely on your equals/hashCode implementation. Use only immutable, identifying fields.\n\n---\n\n## 🧠 Mental Model: HashSet = HashMap with Dummy Values\n\nThe simplest way to understand HashSet is to see what it actually is:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ HASHSET = HASHMAP WRAPPER │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ When you do: HashSet internally does: │\n│ ───────────────────────────────────────────────────── │\n│ set.add(\"Apple\") → map.put(\"Apple\", PRESENT) │\n│ set.contains(\"Apple\") → map.containsKey(\"Apple\") │\n│ set.remove(\"Apple\") → map.remove(\"Apple\") │\n│ set.size() → map.size() │\n│ set.isEmpty() → map.isEmpty() │\n│ set.iterator() → map.keySet().iterator() │\n│ │\n│ Where PRESENT is: │\n│ private static final Object PRESENT = new Object(); │\n│ │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ Internal HashMap │ │\n│ │ ┌───────────┬─────────┐ │ │\n│ │ │ Key │ Value │ │ │\n│ │ ├───────────┼─────────┤ │ │\n│ │ │ \"Apple\" │ PRESENT │ │ │\n│ │ │ \"Banana\" │ PRESENT │ │ │\n│ │ │ \"Cherry\" │ PRESENT │ │ │\n│ │ └───────────┴─────────┘ │ │\n│ │ │ │\n│ │ All values are the SAME dummy object (PRESENT) │ │\n│ │ Only keys matter - they ARE the set elements │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**Key insight:** HashSet is a thin wrapper that delegates everything to HashMap. If you understand HashMap (Part 12-13), you already understand HashSet.\n\n---\n\n## 🔬 Deep Dive\n\n### 1. The Internal Structure\n\n```java\n// ✅ Simplified from JDK source\npublic class HashSet extends AbstractSet\n implements Set, Cloneable, Serializable {\n\n // The backing HashMap\n private transient HashMap map;\n\n // Dummy value to associate with each key\n private static final Object PRESENT = new Object();\n\n // Constructors delegate to HashMap\n public HashSet() {\n map = new HashMap<>();\n }\n\n public HashSet(int initialCapacity) {\n map = new HashMap<>(initialCapacity);\n }\n\n public HashSet(int initialCapacity, float loadFactor) {\n map = new HashMap<>(initialCapacity, loadFactor);\n }\n\n public HashSet(Collection c) {\n map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16));\n addAll(c);\n }\n}\n```\n\n### 2. Core Operations\n\nEvery HashSet operation is a HashMap operation:\n\n```java\n// ✅ add() - uses put() return value to detect duplicates\npublic boolean add(E e) {\n return map.put(e, PRESENT) == null;\n // put() returns previous value:\n // - null if key was new (successfully added)\n // - PRESENT if key existed (duplicate, not added)\n}\n\n// ✅ remove() - delegates to map.remove()\npublic boolean remove(Object o) {\n return map.remove(o) == PRESENT;\n // remove() returns the old value:\n // - PRESENT if key existed (successfully removed)\n // - null if key didn't exist\n}\n\n// ✅ contains() - delegates to containsKey()\npublic boolean contains(Object o) {\n return map.containsKey(o);\n}\n\n// ✅ size(), isEmpty() - delegate to map\npublic int size() {\n return map.size();\n}\n\npublic boolean isEmpty() {\n return map.isEmpty();\n}\n\n// ✅ iterator() - iterates over keys\npublic Iterator iterator() {\n return map.keySet().iterator();\n}\n\n// ✅ clear() - clears the map\npublic void clear() {\n map.clear();\n}\n```\n\n### 3. Why PRESENT and Not Null?\n\nYou might wonder: why use a dummy `PRESENT` object instead of `null`?\n\n```java\n// ❌ If HashSet used null as the value:\npublic boolean add(E e) {\n return map.put(e, null) == null; // Problem!\n}\n\n// put() returns null in TWO cases:\n// 1. Key was new (no previous mapping)\n// 2. Key existed but had null value\n\n// Can't distinguish between \"added new\" and \"was already there with null value\"\n```\n\n```java\n// ✅ With PRESENT:\npublic boolean add(E e) {\n return map.put(e, PRESENT) == null; // Unambiguous!\n}\n\n// put() returns null only when key was new\n// put() returns PRESENT when key existed\n```\n\n### 4. Iteration Order: Why It's Unpredictable\n\nHashSet iteration follows HashMap's bucket order:\n\n```java\nSet set = new HashSet<>();\nset.add(\"Apple\");\nset.add(\"Banana\");\nset.add(\"Cherry\");\n\n// Iteration order is NOT alphabetical, NOT insertion order!\nfor (String s : set) {\n System.out.println(s);\n}\n// Might print: Banana, Cherry, Apple\n// Or: Cherry, Apple, Banana\n// Depends on hash codes and bucket distribution\n```\n\n**Why?** The iterator walks through the bucket array sequentially, returning elements from each non-empty bucket. The order depends on:\n1. Hash codes of elements\n2. Current capacity of the map\n3. Hash function's bit mixing\n\n```text\nHashSet iteration order:\n\nBucket array:\n[0] → null\n[1] → \"Banana\"\n[2] → null\n[3] → \"Cherry\" → \"Apple\" (collision chain)\n[4] → null\n...\n\nIterator walks: bucket 1 → bucket 3 → ...\nOutput: Banana, Cherry, Apple\n```\n\n**If you need predictable order:**\n- **Insertion order:** Use `LinkedHashSet`\n- **Sorted order:** Use `TreeSet`\n\n### 5. Set Algebra Operations\n\nHashSet supports standard set operations through Collection methods:\n\n```java\nSet set1 = new HashSet<>(Arrays.asList(\"A\", \"B\", \"C\", \"D\"));\nSet set2 = new HashSet<>(Arrays.asList(\"C\", \"D\", \"E\", \"F\"));\n\n// ✅ UNION: All elements from both sets\nSet union = new HashSet<>(set1);\nunion.addAll(set2);\n// Result: [A, B, C, D, E, F]\n\n// ✅ INTERSECTION: Elements in both sets\nSet intersection = new HashSet<>(set1);\nintersection.retainAll(set2);\n// Result: [C, D]\n\n// ✅ DIFFERENCE: Elements in set1 but not in set2\nSet difference = new HashSet<>(set1);\ndifference.removeAll(set2);\n// Result: [A, B]\n\n// ✅ SYMMETRIC DIFFERENCE: Elements in either but not both\nSet symmetricDiff = new HashSet<>(set1);\nsymmetricDiff.addAll(set2);\nSet temp = new HashSet<>(set1);\ntemp.retainAll(set2);\nsymmetricDiff.removeAll(temp);\n// Result: [A, B, E, F]\n```\n\n**Performance note:** These operations are O(n) where n is the size of the smaller set (for intersection/difference) or both sets (for union).\n\n### 6. Initial Capacity Planning\n\nLike HashMap, HashSet benefits from proper initial capacity:\n\n```java\n// ❌ Default capacity for large dataset\nSet ids = new HashSet<>(); // Capacity: 16\nfor (String id : millionIds) {\n ids.add(id); // Multiple resizes!\n}\n\n// ✅ Pre-sized for expected elements\nint expectedSize = 1_000_000;\nint capacity = (int) (expectedSize / 0.75) + 1; // Account for load factor\nSet ids = new HashSet<>(capacity);\n```\n\n**Formula:** `capacity = (int)(expectedSize / loadFactor) + 1`\n\nWith default load factor 0.75:\n- 1,000 elements → capacity ~1,334\n- 10,000 elements → capacity ~13,334\n- 1,000,000 elements → capacity ~1,333,334\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Mutable Elements in HashSet\n\n❌ **Problem:**\n```java\nSet> setOfLists = new HashSet<>();\n\nList list = new ArrayList<>();\nlist.add(\"A\");\nsetOfLists.add(list);\n\nSystem.out.println(setOfLists.contains(list)); // true\n\nlist.add(\"B\"); // Modify the list!\n\nSystem.out.println(setOfLists.contains(list)); // false!\n// List is \"lost\" - different hashCode, in wrong bucket\n```\n\n✅ **Solution:**\n```java\n// Option 1: Use immutable elements\nSet> setOfLists = new HashSet<>();\nsetOfLists.add(List.of(\"A\")); // Immutable list\nsetOfLists.add(List.of(\"A\", \"B\"));\n\n// Option 2: Defensive copy on add\nSet> setOfLists = new HashSet<>();\nsetOfLists.add(new ArrayList<>(mutableList)); // Copy\n\n// Option 3: Use different data structure for key\nrecord ListWrapper(List items) {\n @Override public int hashCode() {\n return items.hashCode(); // Still has mutation problem\n }\n}\n// Better: use immutable wrapper or different identity\n```\n\n---\n\n### Mistake 2: Incorrect equals/hashCode Leading to \"Duplicates\"\n\n❌ **Problem:**\n```java\npublic class Person {\n private String name;\n private int age;\n\n // Only equals() implemented, no hashCode()!\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof Person)) return false;\n Person p = (Person) o;\n return name.equals(p.name) && age == p.age;\n }\n // hashCode() not overridden - uses Object.hashCode() (memory address)\n}\n\nSet people = new HashSet<>();\npeople.add(new Person(\"Alice\", 30));\npeople.add(new Person(\"Alice\", 30)); // \"Duplicate\" added!\n\nSystem.out.println(people.size()); // 2! Not 1!\n```\n\n✅ **Solution:**\n```java\npublic class Person {\n private String name;\n private int age;\n\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof Person)) return false;\n Person p = (Person) o;\n return name.equals(p.name) && age == p.age;\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(name, age); // Consistent with equals!\n }\n}\n\nSet people = new HashSet<>();\npeople.add(new Person(\"Alice\", 30));\npeople.add(new Person(\"Alice\", 30)); // Duplicate detected\n\nSystem.out.println(people.size()); // 1 - correct!\n```\n\n---\n\n### Mistake 3: Expecting Iteration Order\n\n❌ **Problem:**\n```java\nSet set = new HashSet<>();\nset.add(\"First\");\nset.add(\"Second\");\nset.add(\"Third\");\n\n// Assuming insertion order\nList list = new ArrayList<>(set);\nString first = list.get(0); // Might not be \"First\"!\n```\n\n✅ **Solution:**\n```java\n// Use LinkedHashSet for insertion order\nSet set = new LinkedHashSet<>();\nset.add(\"First\");\nset.add(\"Second\");\nset.add(\"Third\");\n\nList list = new ArrayList<>(set);\nString first = list.get(0); // Guaranteed to be \"First\"\n\n// Or use TreeSet for sorted order\nSet sorted = new TreeSet<>();\nsorted.add(\"Cherry\");\nsorted.add(\"Apple\");\nsorted.add(\"Banana\");\n// Iteration: Apple, Banana, Cherry (sorted)\n```\n\n---\n\n### Mistake 4: Inefficient Duplicate Detection\n\n❌ **Problem:**\n```java\n// O(n²) duplicate detection with List\nList items = loadMillionItems();\nList unique = new ArrayList<>();\n\nfor (String item : items) {\n if (!unique.contains(item)) { // O(n) for each check!\n unique.add(item);\n }\n}\n// Total: O(n²)\n```\n\n✅ **Solution:**\n```java\n// O(n) with HashSet\nList items = loadMillionItems();\nSet unique = new LinkedHashSet<>(items); // Preserves first occurrence order\nList result = new ArrayList<>(unique);\n// Total: O(n)\n\n// Or simply:\nList unique = items.stream()\n .distinct()\n .toList();\n// distinct() uses Set internally\n```\n\n---\n\n### Mistake 5: Using HashSet with Non-Hashable Types\n\n❌ **Problem:**\n```java\n// Arrays don't override hashCode() properly\nSet arraySet = new HashSet<>();\narraySet.add(new int[]{1, 2, 3});\narraySet.add(new int[]{1, 2, 3});\n\nSystem.out.println(arraySet.size()); // 2! Arrays use identity hashCode\n```\n\n✅ **Solution:**\n```java\n// Option 1: Use List instead of array\nSet> listSet = new HashSet<>();\nlistSet.add(List.of(1, 2, 3));\nlistSet.add(List.of(1, 2, 3));\nSystem.out.println(listSet.size()); // 1 - List has proper hashCode\n\n// Option 2: Wrap arrays in a class with proper hashCode\nrecord IntArrayWrapper(int[] array) {\n @Override\n public int hashCode() {\n return Arrays.hashCode(array);\n }\n\n @Override\n public boolean equals(Object o) {\n return o instanceof IntArrayWrapper w &&\n Arrays.equals(array, w.array);\n }\n}\n```\n\n---\n\n## 🐛 Debug This: The Mystery Duplicates\n\nA developer reports: \"I'm using HashSet but still getting duplicates!\"\n\n```java\npublic class CacheKey {\n private String region;\n private String key;\n\n public CacheKey(String region, String key) {\n this.region = region;\n this.key = key;\n }\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (o == null || getClass() != o.getClass()) return false;\n CacheKey cacheKey = (CacheKey) o;\n return region.equals(cacheKey.region) && key.equals(cacheKey.key);\n }\n\n // Developer \"forgot\" hashCode but added this instead:\n @Override\n public String toString() {\n return region + \":\" + key;\n }\n}\n\n// Usage:\nSet keys = new HashSet<>();\nkeys.add(new CacheKey(\"US\", \"user:123\"));\nkeys.add(new CacheKey(\"US\", \"user:123\"));\n\nSystem.out.println(\"Size: \" + keys.size()); // Prints: 2\nSystem.out.println(\"Contains: \" + keys.contains(new CacheKey(\"US\", \"user:123\"))); // false!\n```\n\n**Why are there duplicates? Find and fix the bug.**\n\n---\n\n**✅ Solution:**\n\nThe developer implemented `equals()` but not `hashCode()`. The `toString()` method is irrelevant for Set behavior.\n\nWithout a proper `hashCode()`:\n1. Each `CacheKey` uses `Object.hashCode()` (memory address)\n2. Two equal CacheKeys have different hash codes\n3. They land in different buckets\n4. HashSet never calls `equals()` because they're in different buckets\n\n```java\n// ✅ Fixed CacheKey\npublic class CacheKey {\n private final String region;\n private final String key;\n\n public CacheKey(String region, String key) {\n this.region = Objects.requireNonNull(region);\n this.key = Objects.requireNonNull(key);\n }\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (o == null || getClass() != o.getClass()) return false;\n CacheKey cacheKey = (CacheKey) o;\n return region.equals(cacheKey.region) && key.equals(cacheKey.key);\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(region, key); // ✅ Added!\n }\n\n @Override\n public String toString() {\n return region + \":\" + key;\n }\n}\n\n// Now works correctly:\nSet keys = new HashSet<>();\nkeys.add(new CacheKey(\"US\", \"user:123\"));\nkeys.add(new CacheKey(\"US\", \"user:123\"));\n\nSystem.out.println(\"Size: \" + keys.size()); // 1\nSystem.out.println(\"Contains: \" + keys.contains(new CacheKey(\"US\", \"user:123\"))); // true\n```\n\n**Better approach - use Record:**\n```java\npublic record CacheKey(String region, String key) {\n // equals() and hashCode() generated automatically!\n}\n```\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Efficient Deduplication\n⭐⭐ Difficulty: Medium | ⏱️ Time: 10 minutes\n\n**Task:** Remove duplicates from a list while preserving the order of first occurrences.\n\n```java\npublic class Deduplication {\n // TODO: Remove duplicates, preserve first occurrence order\n public static List removeDuplicates(List list) {\n // Return list with duplicates removed\n }\n}\n\n// Example:\n// Input: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]\n// Output: [3, 1, 4, 5, 9, 2, 6]\n```\n\n**✅ Solution:**\n\n```java\npublic class Deduplication {\n\n // Option 1: LinkedHashSet (cleanest)\n public static List removeDuplicates(List list) {\n return new ArrayList<>(new LinkedHashSet<>(list));\n }\n\n // Option 2: Stream API\n public static List removeDuplicatesStream(List list) {\n return list.stream()\n .distinct()\n .toList();\n }\n\n // Option 3: Manual with Set tracking\n public static List removeDuplicatesManual(List list) {\n Set seen = new HashSet<>();\n List result = new ArrayList<>();\n\n for (E element : list) {\n if (seen.add(element)) { // add returns true if new\n result.add(element);\n }\n }\n\n return result;\n }\n\n public static void main(String[] args) {\n List input = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);\n\n System.out.println(\"Input: \" + input);\n System.out.println(\"Deduplicated: \" + removeDuplicates(input));\n // Output: [3, 1, 4, 5, 9, 2, 6]\n }\n}\n```\n\n---\n\n### Exercise 2: Find Duplicates Between Lists\n⭐⭐ Difficulty: Medium | ⏱️ Time: 15 minutes\n\n**Task:** Find elements that appear in both lists efficiently.\n\n```java\npublic class DuplicateFinder {\n // TODO: Find elements in both lists (intersection)\n public static Set findCommon(List list1, List list2) {\n // Return set of common elements\n }\n\n // TODO: Find elements unique to list1 (difference)\n public static Set findUnique(List list1, List list2) {\n // Return elements in list1 but not in list2\n }\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class DuplicateFinder {\n\n // Intersection: elements in both lists\n public static Set findCommon(List list1, List list2) {\n // Convert smaller list to set for better performance\n if (list1.size() > list2.size()) {\n List temp = list1;\n list1 = list2;\n list2 = temp;\n }\n\n Set set1 = new HashSet<>(list1);\n Set result = new HashSet<>();\n\n for (E element : list2) {\n if (set1.contains(element)) {\n result.add(element);\n }\n }\n\n return result;\n }\n\n // Alternative using retainAll\n public static Set findCommonRetainAll(List list1, List list2) {\n Set result = new HashSet<>(list1);\n result.retainAll(list2);\n return result;\n }\n\n // Difference: elements in list1 but not list2\n public static Set findUnique(List list1, List list2) {\n Set result = new HashSet<>(list1);\n result.removeAll(list2);\n return result;\n }\n\n public static void main(String[] args) {\n List list1 = Arrays.asList(1, 2, 3, 4, 5);\n List list2 = Arrays.asList(4, 5, 6, 7, 8);\n\n System.out.println(\"Common: \" + findCommon(list1, list2)); // [4, 5]\n System.out.println(\"Unique to list1: \" + findUnique(list1, list2)); // [1, 2, 3]\n System.out.println(\"Unique to list2: \" + findUnique(list2, list1)); // [6, 7, 8]\n }\n}\n```\n\n---\n\n### Exercise 3: Set Algebra Operations\n⭐⭐⭐ Difficulty: Medium | ⏱️ Time: 15 minutes\n\n**Task:** Implement all standard set operations.\n\n```java\npublic class SetAlgebra {\n\n public static Set union(Set a, Set b) { }\n public static Set intersection(Set a, Set b) { }\n public static Set difference(Set a, Set b) { }\n public static Set symmetricDifference(Set a, Set b) { }\n public static boolean isSubset(Set subset, Set superset) { }\n public static boolean isDisjoint(Set a, Set b) { }\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class SetAlgebra {\n\n // Union: A ∪ B (all elements in either set)\n public static Set union(Set a, Set b) {\n Set result = new HashSet<>(a);\n result.addAll(b);\n return result;\n }\n\n // Intersection: A ∩ B (elements in both sets)\n public static Set intersection(Set a, Set b) {\n Set result = new HashSet<>(a);\n result.retainAll(b);\n return result;\n }\n\n // Difference: A - B (elements in A but not B)\n public static Set difference(Set a, Set b) {\n Set result = new HashSet<>(a);\n result.removeAll(b);\n return result;\n }\n\n // Symmetric Difference: A △ B (elements in either but not both)\n public static Set symmetricDifference(Set a, Set b) {\n Set result = new HashSet<>(a);\n for (E element : b) {\n if (!result.add(element)) { // If already present\n result.remove(element); // Remove it (was in both)\n }\n }\n return result;\n }\n\n // Alternative symmetric difference\n public static Set symmetricDifferenceAlt(Set a, Set b) {\n Set union = union(a, b);\n Set intersection = intersection(a, b);\n union.removeAll(intersection);\n return union;\n }\n\n // Subset check: A ⊆ B\n public static boolean isSubset(Set subset, Set superset) {\n return superset.containsAll(subset);\n }\n\n // Disjoint check: A ∩ B = ∅\n public static boolean isDisjoint(Set a, Set b) {\n // Use smaller set for iteration\n if (a.size() > b.size()) {\n Set temp = a;\n a = b;\n b = temp;\n }\n\n for (E element : a) {\n if (b.contains(element)) {\n return false;\n }\n }\n return true;\n }\n\n public static void main(String[] args) {\n Set a = Set.of(1, 2, 3, 4);\n Set b = Set.of(3, 4, 5, 6);\n\n System.out.println(\"A: \" + a);\n System.out.println(\"B: \" + b);\n System.out.println(\"Union: \" + union(a, b)); // [1,2,3,4,5,6]\n System.out.println(\"Intersection: \" + intersection(a, b)); // [3,4]\n System.out.println(\"A - B: \" + difference(a, b)); // [1,2]\n System.out.println(\"Symmetric Diff: \" + symmetricDifference(a, b)); // [1,2,5,6]\n System.out.println(\"A ⊆ B: \" + isSubset(a, b)); // false\n System.out.println(\"Disjoint: \" + isDisjoint(a, b)); // false\n }\n}\n```\n\n---\n\n### Exercise 4: Custom Hash Distribution Analyzer\n⭐⭐⭐ Difficulty: Medium-Hard | ⏱️ Time: 20 minutes\n\n**Task:** Create a utility to analyze how well elements are distributed across HashSet buckets.\n\n```java\npublic class HashSetAnalyzer {\n public static void analyze(Set set) {\n // TODO: Print distribution statistics\n // - Number of buckets\n // - Number of collisions\n // - Longest chain\n // - Average chain length\n }\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class HashSetAnalyzer {\n\n public static void analyze(Set set) throws Exception {\n if (!(set instanceof HashSet)) {\n System.out.println(\"Only HashSet supported\");\n return;\n }\n\n HashSet hashSet = (HashSet) set;\n\n // Access the internal HashMap\n Field mapField = HashSet.class.getDeclaredField(\"map\");\n mapField.setAccessible(true);\n HashMap map = (HashMap) mapField.get(hashSet);\n\n // Access HashMap's table\n Field tableField = HashMap.class.getDeclaredField(\"table\");\n tableField.setAccessible(true);\n Object[] table = (Object[]) tableField.get(map);\n\n if (table == null) {\n System.out.println(\"Empty HashSet\");\n return;\n }\n\n int totalBuckets = table.length;\n int usedBuckets = 0;\n int collisionBuckets = 0;\n int maxChain = 0;\n int totalElements = 0;\n\n for (Object bucket : table) {\n if (bucket != null) {\n usedBuckets++;\n int chainLength = countChain(bucket);\n totalElements += chainLength;\n if (chainLength > 1) {\n collisionBuckets++;\n }\n maxChain = Math.max(maxChain, chainLength);\n }\n }\n\n double loadFactor = (double) totalElements / totalBuckets;\n double avgChain = usedBuckets > 0 ? (double) totalElements / usedBuckets : 0;\n\n System.out.println(\"=== HashSet Analysis ===\");\n System.out.printf(\"Total buckets: %d%n\", totalBuckets);\n System.out.printf(\"Used buckets: %d (%.1f%%)%n\", usedBuckets, 100.0 * usedBuckets / totalBuckets);\n System.out.printf(\"Collision buckets: %d%n\", collisionBuckets);\n System.out.printf(\"Total elements: %d%n\", totalElements);\n System.out.printf(\"Load factor: %.2f%n\", loadFactor);\n System.out.printf(\"Max chain length: %d%n\", maxChain);\n System.out.printf(\"Avg chain length: %.2f%n\", avgChain);\n }\n\n private static int countChain(Object node) throws Exception {\n int count = 0;\n Field nextField = null;\n\n while (node != null) {\n count++;\n if (nextField == null) {\n try {\n nextField = node.getClass().getDeclaredField(\"next\");\n nextField.setAccessible(true);\n } catch (NoSuchFieldException e) {\n break;\n }\n }\n node = nextField.get(node);\n }\n return count;\n }\n\n public static void main(String[] args) throws Exception {\n Set set = new HashSet<>();\n for (int i = 0; i < 1000; i++) {\n set.add(\"item\" + i);\n }\n analyze(set);\n }\n}\n```\n\n---\n\n### Exercise 5: EnumSet Comparison\n⭐⭐ Difficulty: Medium | ⏱️ Time: 10 minutes\n\n**Task:** Compare HashSet and EnumSet for enum values.\n\n```java\npublic class EnumSetDemo {\n enum Permission {\n READ, WRITE, DELETE, ADMIN, SUPER_ADMIN\n }\n\n // TODO: Demonstrate why EnumSet is better than HashSet\n public static void comparePerformance() {\n // Create both types with same elements\n // Compare memory and speed\n }\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class EnumSetDemo {\n enum Permission {\n READ, WRITE, DELETE, ADMIN, SUPER_ADMIN\n }\n\n public static void main(String[] args) {\n // HashSet approach\n Set hashSet = new HashSet<>();\n hashSet.add(Permission.READ);\n hashSet.add(Permission.WRITE);\n hashSet.add(Permission.ADMIN);\n\n // EnumSet approach\n Set enumSet = EnumSet.of(Permission.READ, Permission.WRITE, Permission.ADMIN);\n\n System.out.println(\"=== Feature Comparison ===\");\n System.out.println(\"HashSet: \" + hashSet);\n System.out.println(\"EnumSet: \" + enumSet);\n\n System.out.println(\"\\n=== Memory ===\");\n // EnumSet uses bit vector - just 1 long for up to 64 enum values\n // HashSet uses HashMap with Entry objects\n System.out.println(\"EnumSet: ~8 bytes (one long)\");\n System.out.println(\"HashSet: ~200+ bytes (HashMap overhead + Entry objects)\");\n\n System.out.println(\"\\n=== Performance ===\");\n int iterations = 10_000_000;\n\n // Benchmark contains()\n long startHash = System.nanoTime();\n for (int i = 0; i < iterations; i++) {\n hashSet.contains(Permission.WRITE);\n }\n long hashTime = System.nanoTime() - startHash;\n\n long startEnum = System.nanoTime();\n for (int i = 0; i < iterations; i++) {\n enumSet.contains(Permission.WRITE);\n }\n long enumTime = System.nanoTime() - startEnum;\n\n System.out.printf(\"HashSet.contains(): %d ms%n\", hashTime / 1_000_000);\n System.out.printf(\"EnumSet.contains(): %d ms%n\", enumTime / 1_000_000);\n System.out.printf(\"EnumSet is %.1fx faster%n\", (double) hashTime / enumTime);\n\n System.out.println(\"\\n=== EnumSet Special Operations ===\");\n // EnumSet has useful factory methods\n Set all = EnumSet.allOf(Permission.class);\n Set none = EnumSet.noneOf(Permission.class);\n Set complement = EnumSet.complementOf(enumSet);\n Set range = EnumSet.range(Permission.WRITE, Permission.ADMIN);\n\n System.out.println(\"All: \" + all);\n System.out.println(\"None: \" + none);\n System.out.println(\"Complement: \" + complement);\n System.out.println(\"Range WRITE-ADMIN: \" + range);\n }\n}\n\n// Typical output:\n// EnumSet is 2-5x faster than HashSet for contains()\n// EnumSet uses ~25x less memory\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### HashSet Internals\n\n```text\nHashSet = HashMap wrapper\n\n┌─────────────────────────────────────────────┐\n│ HashSet │\n│ └── HashMap │\n│ └── table: Node[] │\n│ └── Each node stores: │\n│ - key (your element) │\n│ - value (always PRESENT) │\n│ - hash │\n│ - next │\n└─────────────────────────────────────────────┘\n```\n\n### Performance Characteristics\n\n| Operation | Average | Worst Case | Notes |\n|-----------|---------|------------|-------|\n| add(E) | O(1) | O(n) | Worst with many collisions |\n| remove(E) | O(1) | O(n) | Worst with many collisions |\n| contains(E) | O(1) | O(n) | Worst with many collisions |\n| size() | O(1) | O(1) | Just returns field |\n| isEmpty() | O(1) | O(1) | Checks size == 0 |\n| iterator.next() | O(1)* | O(n) | *Amortized across full iteration |\n\n### When to Use Which Set\n\n| Use Case | Best Set | Why |\n|----------|----------|-----|\n| Default, no ordering | HashSet | O(1) operations |\n| Maintain insertion order | LinkedHashSet | O(1) + predictable iteration |\n| Sorted iteration | TreeSet | O(log n) but sorted |\n| Enum values | EnumSet | Bit vector, extremely fast |\n| Thread-safe | ConcurrentHashMap.newKeySet() | Concurrent access |\n| Immutable | Set.of() | No modification possible |\n\n### Critical Rules\n\n1. **Always override both equals() AND hashCode()** for elements\n2. **Use immutable elements** or never modify after adding\n3. **Pre-size for large sets** to avoid resize overhead\n4. **Don't rely on iteration order** - use LinkedHashSet if needed\n5. **Use EnumSet for enum values** - much more efficient\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question #1: How does HashSet ensure uniqueness?\n\n**What interviewers want to hear**: Understanding that HashSet is backed by HashMap.\n\n**Strong answer**: HashSet uses a HashMap internally where elements are keys and values are a constant dummy object (PRESENT). When you call `add(element)`, it actually calls `map.put(element, PRESENT)`. HashMap ensures key uniqueness - if the key already exists, put() returns the old value (PRESENT), and HashSet's add() returns false. If the key is new, put() returns null, and add() returns true. The uniqueness check uses hashCode() to find the bucket, then equals() to check for duplicates in that bucket.\n\n---\n\n### Question #2: What is the time complexity of add/remove/contains in HashSet?\n\n**What interviewers want to hear**: Understanding of average vs worst case.\n\n**Strong answer**: Average case is O(1) for all three operations because they're backed by HashMap's O(1) bucket lookup. However, worst case is O(n) when all elements hash to the same bucket (hash collision attack scenario). In Java 8+, this worst case improves to O(log n) due to tree bins that activate when a bucket has 8+ entries. The O(1) depends on a good hash function distributing elements across buckets evenly.\n\n---\n\n### Question #3: Why doesn't HashSet maintain insertion order?\n\n**What interviewers want to hear**: Understanding of hash-based storage.\n\n**Strong answer**: HashSet stores elements in buckets determined by hash code, not insertion order. The iterator walks through the bucket array sequentially, returning elements from each non-empty bucket. This order depends on hash codes and current capacity - adding more elements can trigger resize, which redistributes elements to different buckets, changing iteration order. If you need insertion order, use LinkedHashSet, which maintains a doubly-linked list through all entries in addition to the hash table.\n\n---\n\n### Question #4: What happens if you modify an object after adding it to a HashSet?\n\n**What interviewers want to hear**: Understanding of the mutable element trap.\n\n**Strong answer**: If modification changes the object's hashCode(), the object becomes \"lost\" in the HashSet. It's still physically present in some bucket, but that bucket no longer matches its current hashCode. Operations like contains(), remove(), and even iteration may behave unexpectedly. The object might appear during iteration (walking all buckets) but contains() returns false (looking in wrong bucket). This is why HashSet elements should be immutable, or at least their fields used in hashCode() should never change after insertion.\n\n---\n\n### Question #5: What's the difference between HashSet and TreeSet?\n\n**What interviewers want to hear**: Understanding of different Set implementations.\n\n**Strong answer**: HashSet uses a hash table (HashMap internally), providing O(1) average operations but no ordering guarantees. TreeSet uses a red-black tree (TreeMap internally), providing O(log n) operations but maintaining sorted order. HashSet requires hashCode() and equals(); TreeSet requires Comparable or a Comparator. Choose HashSet for fastest operations when order doesn't matter; choose TreeSet when you need sorted iteration or NavigableSet methods like floor(), ceiling(), subSet().\n\n---\n\n### Question #6: When should you use EnumSet instead of HashSet?\n\n**What interviewers want to hear**: Knowledge of specialized collections.\n\n**Strong answer**: Always use EnumSet for sets of enum values. EnumSet uses a bit vector representation - each enum value maps to a bit position, so a set of up to 64 enum values fits in a single long. This makes operations like add, remove, and contains simple bit operations - O(1) with tiny constants. Memory usage is minimal (8 bytes vs hundreds for HashSet). EnumSet also provides useful factory methods like `EnumSet.allOf()`, `complementOf()`, and `range()`. The only reason to use HashSet is when you need the exact HashSet class for some API requirement.\n\n---\n\n## 🏁 Conclusion\n\nHashSet is deceptively simple - it's just a HashMap wrapper. But understanding this relationship unlocks deeper knowledge:\n\n- Every HashSet operation is a HashMap operation\n- Uniqueness depends on equals() AND hashCode()\n- Mutable elements are dangerous\n- Iteration order is unpredictable\n\n**Key takeaways:**\n\n1. **HashSet = HashMap with dummy values** - understand one, understand both\n2. **Override both equals() AND hashCode()** - missing either breaks uniqueness\n3. **Use immutable elements** - mutation causes \"lost\" objects\n4. **Pre-size large sets** - inherits HashMap's resize behavior\n5. **Choose the right Set** - LinkedHashSet for order, TreeSet for sorting, EnumSet for enums\n\n**Your next step:** Continue to Part 10 (TreeSet) to understand sorted sets and NavigableSet operations, or Part 11 (Specialized Sets) to explore EnumSet and CopyOnWriteArraySet.\n\n---\n\n## 📅 Review Schedule for This Article\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review HashSet = HashMap relationship | 5 min |\n| Day 3 | Redo Exercise 2 (Find Duplicates) | 15 min |\n| Day 7 | Answer interview questions without looking | 10 min |\n| Day 14 | Redo Debug This exercise | 10 min |\n| Day 30 | Review Set comparison table | 5 min |\n\n---\n\n*Next in series: [Part 10: TreeSet & NavigableSet Operations]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.938473Z","createdAt","2026-06-10T07:19:25.939290Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",21,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder",9,"author",{"_31":55,"_100":57,"_101":102,"_103":104,"_105":-5,"_106":-5,"_107":-5,"_108":-5,"_109":-5},"category",{"_31":62,"_73":59,"_35":91,"_76":98,"_99":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":95,"_73":96,"_35":97},{"_31":92,"_73":93,"_35":94},{"_31":90,"_73":59,"_35":91},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},340,"Uniqueness","uniqueness",338,"Set","set",14,"java",337,"Hashset","hashset",339,"Hashing","hashing","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]