HashSet is one of the most commonly used Set implementations in Java that uses a hash table for storage. Let's explore its internal implementation in detail.

1. HashSet Class Structure

Basic Class Declaration and Fields

import java.util.*; public class HashSetInternal<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // Backing HashMap instance private transient HashMap<E, Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); // Constructors public HashSetInternal() { map = new HashMap<>(); } public HashSetInternal(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16)); addAll(c); } public HashSetInternal(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSetInternal(int initialCapacity) { map = new HashMap<>(initialCapacity); } // Package-private constructor for LinkedHashSet HashSetInternal(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } }

2. Internal Data Structure

HashSet uses HashMap Internally

public class HashSetStructureDemo { public static void main(String[] args) { // Creating a HashSet HashSet<String> set = new HashSet<>(); // Internally, HashSet creates a HashMap // HashMap<String, Object> map = new HashMap<>(); // Object PRESENT = new Object(); // Dummy object // When we add elements to HashSet: set.add("Apple"); // Internally: map.put("Apple", PRESENT) -> returns null (success) set.add("Banana"); // Internally: map.put("Banana", PRESENT) -> returns null (success) set.add("Apple"); // Internally: map.put("Apple", PRESENT) -> returns PRESENT (already exists) // So add() returns false System.out.println("HashSet: " + set); System.out.println("Size: " + set.size()); } } // Visual representation of HashSet internal structure class HashSetInternalView { /* HashSet Internals: HashSet<String> set = new HashSet<>(); Internally: - HashMap<E, Object> map = new HashMap<>(); - Object PRESENT = new Object(); Operation: set.add("Apple") ↳ map.put("Apple", PRESENT) Operation: set.contains("Apple") ↳ map.containsKey("Apple") Operation: set.remove("Apple") ↳ map.remove("Apple") == PRESENT The HashMap stores: Key: "Apple" Value: PRESENT Key: "Banana" Value: PRESENT Key: "Cherry" Value: PRESENT */ }

3. Core Methods Implementation

Complete HashSet Implementation

import java.util.*; import java.io.*; public class CustomHashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable { private transient HashMap<E, Object> map; private static final Object PRESENT = new Object(); // Constructors public CustomHashSet() { map = new HashMap<>(); } public CustomHashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16)); addAll(c); } public CustomHashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public CustomHashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } // Core Methods @Override public boolean add(E e) { System.out.println("Adding element: " + e); boolean added = (map.put(e, PRESENT) == null); System.out.println("Element " + e + " added: " + added); return added; } @Override public boolean remove(Object o) { System.out.println("Removing element: " + o); boolean removed = (map.remove(o) == PRESENT); System.out.println("Element " + o + " removed: " + removed); return removed; } @Override public boolean contains(Object o) { boolean contains = map.containsKey(o); System.out.println("Set contains " + o + ": " + contains); return contains; } @Override public int size() { return map.size(); } @Override public boolean isEmpty() { return map.isEmpty(); } @Override public void clear() { System.out.println("Clearing the set"); map.clear(); } @Override public Iterator<E> iterator() { return map.keySet().iterator(); } // Additional utility methods public void printInternalState() { System.out.println("=== HashSet Internal State ==="); System.out.println("Size: " + size()); System.out.println("Backing HashMap size: " + map.size()); System.out.println("Elements: " + this); System.out.println("=============================="); } public static void main(String[] args) { CustomHashSet<String> set = new CustomHashSet<>(); set.printInternalState(); // Add elements set.add("Apple"); set.add("Banana"); set.add("Apple"); // Duplicate set.add("Cherry"); set.printInternalState(); // Check contains set.contains("Banana"); set.contains("Grape"); // Remove elements set.remove("Banana"); set.remove("Grape"); // Non-existent set.printInternalState(); } }

4. Hash Mechanism and Buckets

Understanding Hash Distribution

import java.util.*; public class HashSetHashMechanism { static class Student { String name; int id; Student(String name, int id) { this.name = name; this.id = id; } // Custom hashCode implementation @Override public int hashCode() { System.out.println("Calculating hashCode for: " + name); return Objects.hash(name, id); } // Custom equals implementation @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null || getClass() != obj.getClass()) return false; Student student = (Student) obj; return id == student.id && Objects.equals(name, student.name); } @Override public String toString() { return "Student{name='" + name + "', id=" + id + "}"; } } public static void main(String[] args) { System.out.println("=== HashSet Hash Mechanism Demo ==="); HashSet<Student> studentSet = new HashSet<>(); // Add students - watch hashCode calls Student s1 = new Student("John", 101); Student s2 = new Student("Jane", 102); Student s3 = new Student("John", 101); // Duplicate System.out.println("\n--- Adding Students ---"); studentSet.add(s1); studentSet.add(s2); studentSet.add(s3); // This should not be added System.out.println("\nFinal Set: " + studentSet); System.out.println("Size: " + studentSet.size()); // Demonstrate bucket distribution demonstrateBucketDistribution(); } public static void demonstrateBucketDistribution() { System.out.println("\n=== Bucket Distribution Demo ==="); HashSet<Integer> numberSet = new HashSet<>(16, 0.75f); // Initial capacity 16 // Add numbers and observe their bucket placement for (int i = 0; i < 20; i++) { int number = i * 10; // 0, 10, 20, ..., 190 int hash = Integer.hashCode(number); int bucket = (16 - 1) & hash; // Simulate bucket calculation System.out.printf("Number: %3d, Hash: %d, Bucket: %2d%n", number, hash, bucket); numberSet.add(number); } System.out.println("Final set size: " + numberSet.size()); } }

5. Load Factor and Rehashing

Load Factor Demonstration

import java.util.*; import java.lang.reflect.*; public class HashSetLoadFactorDemo { public static void main(String[] args) throws Exception { System.out.println("=== HashSet Load Factor and Rehashing ==="); // Create HashSet with small initial capacity and load factor HashSet<Integer> set = new HashSet<>(4, 0.5f); // Get internal HashMap capacity using reflection System.out.println("Initial state:"); printInternalState(set); // Add elements and watch rehashing for (int i = 1; i <= 10; i++) { set.add(i); System.out.println("\nAfter adding " + i + ":"); printInternalState(set); // Check if rehashing occurred if (i == 2 || i == 4 || i == 8) { System.out.println(">>> REHASHING likely occurred here! <<<"); } } System.out.println("\nFinal set: " + set); } private static void printInternalState(HashSet<?> set) throws Exception { // Access the internal map Field mapField = HashSet.class.getDeclaredField("map"); mapField.setAccessible(true); HashMap<?, ?> map = (HashMap<?, ?>) mapField.get(set); // Get capacity of the internal HashMap Field tableField = HashMap.class.getDeclaredField("table"); tableField.setAccessible(true); Object[] table = (Object[]) tableField.get(map); int capacity = (table != null) ? table.length : 0; int size = set.size(); float loadFactor = getLoadFactor(map); System.out.printf("Size: %d, Capacity: %d, Load Factor: %.2f, Actual Load: %.2f%n", size, capacity, loadFactor, (float) size / capacity); // Print bucket distribution printBucketDistribution(table, size); } private static float getLoadFactor(HashMap<?, ?> map) throws Exception { Field loadFactorField = HashMap.class.getDeclaredField("loadFactor"); loadFactorField.setAccessible(true); return (Float) loadFactorField.get(map); } private static void printBucketDistribution(Object[] table, int totalSize) { if (table == null) return; int emptyBuckets = 0; int maxChainLength = 0; Map<Integer, Integer> chainLengths = new HashMap<>(); for (Object entry : table) { int chainLength = 0; Object current = entry; while (current != null) { chainLength++; // Get next entry in the chain Field nextField = getField(current.getClass(), "next"); try { current = nextField.get(current); } catch (Exception e) { current = null; } } if (chainLength == 0) { emptyBuckets++; } else { chainLengths.put(chainLength, chainLengths.getOrDefault(chainLength, 0) + 1); maxChainLength = Math.max(maxChainLength, chainLength); } } System.out.printf("Empty buckets: %d/%d (%.1f%%)%n", emptyBuckets, table.length, (emptyBuckets * 100.0 / table.length)); System.out.printf("Max chain length: %d%n", maxChainLength); System.out.println("Chain length distribution: " + chainLengths); } private static Field getField(Class<?> clazz, String fieldName) { try { Field field = clazz.getDeclaredField("fieldName"); field.setAccessible(true); return field; } catch (Exception e) { return null; } } }

6. Iterator Implementation

HashSet Iterator Internal Working

import java.util.*; public class HashSetIteratorInternal { public static void main(String[] args) { System.out.println("=== HashSet Iterator Internal Working ==="); HashSet<String> set = new HashSet<>(); Collections.addAll(set, "Apple", "Banana", "Cherry", "Date", "Elderberry"); System.out.println("Original set: " + set); // Get iterator Iterator<String> iterator = set.iterator(); System.out.println("\nIterating through elements:"); while (iterator.hasNext()) { String element = iterator.next(); System.out.println("Current element: " + element); // Simulate concurrent modification detection if (element.equals("Cherry")) { // This would cause ConcurrentModificationException if uncommented // set.add("Fig"); } } // Demonstrate iterator remove iterator = set.iterator(); System.out.println("\nUsing iterator remove:"); while (iterator.hasNext()) { String element = iterator.next(); if (element.equals("Banana")) { System.out.println("Removing: " + element); iterator.remove(); } } System.out.println("Set after iterator remove: " + set); // Show fail-fast behavior demonstrateFailFast(); } public static void demonstrateFailFast() { System.out.println("\n=== Fail-Fast Iterator Demo ==="); HashSet<Integer> set = new HashSet<>(); for (int i = 1; i <= 5; i++) { set.add(i); } try { Iterator<Integer> iterator = set.iterator(); while (iterator.hasNext()) { Integer num = iterator.next(); System.out.println("Processing: " + num); if (num == 3) { set.add(99); // Structural modification System.out.println("Added new element during iteration"); } } } catch (ConcurrentModificationException e) { System.out.println("Caught ConcurrentModificationException: " + e.getMessage()); } } } // Custom HashSet with detailed iterator logging class LoggingHashSet<E> extends HashSet<E> { @Override public Iterator<E> iterator() { System.out.println("Creating new iterator"); return new LoggingIterator(super.iterator()); } private class LoggingIterator implements Iterator<E> { private final Iterator<E> delegate; private E lastElement; LoggingIterator(Iterator<E> delegate) { this.delegate = delegate; } @Override public boolean hasNext() { boolean hasNext = delegate.hasNext(); System.out.println("hasNext() returned: " + hasNext); return hasNext; } @Override public E next() { lastElement = delegate.next(); System.out.println("next() returned: " + lastElement); return lastElement; } @Override public void remove() { System.out.println("remove() called for: " + lastElement); delegate.remove(); } } public static void main(String[] args) { LoggingHashSet<String> set = new LoggingHashSet<>(); Collections.addAll(set, "One", "Two", "Three"); System.out.println("=== Iterating with Logging ==="); Iterator<String> iterator = set.iterator(); while (iterator.hasNext()) { String element = iterator.next(); if (element.equals("Two")) { iterator.remove(); } } System.out.println("Final set: " + set); } }

7. Performance Analysis

HashSet Performance Characteristics

import java.util.*; public class HashSetPerformanceAnalysis { private static final int TEST_SIZE = 100000; public static void main(String[] args) { System.out.println("HashSet Performance Analysis"); System.out.println("Test Size: " + TEST_SIZE + " elements"); System.out.println("====================================="); testAddPerformance(); testContainsPerformance(); testRemovePerformance(); testIterationPerformance(); testMemoryUsage(); } public static void testAddPerformance() { System.out.println("\n=== Add Operations ==="); HashSet<Integer> set = new HashSet<>(); // Sequential adds long start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { set.add(i); } long end = System.nanoTime(); System.out.printf("Sequential add: %.2f ms%n", (end - start) / 1_000_000.0); // Random adds set.clear(); Random random = new Random(); start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { set.add(random.nextInt(TEST_SIZE * 10)); } end = System.nanoTime(); System.out.printf("Random add: %.2f ms%n", (end - start) / 1_000_000.0); // Duplicate adds start = System.nanoTime(); int duplicates = 0; for (int i = 0; i < TEST_SIZE; i++) { if (!set.add(i)) { // Try to add existing elements duplicates++; } } end = System.nanoTime(); System.out.printf("Duplicate add (%d duplicates): %.2f ms%n", duplicates, (end - start) / 1_000_000.0); } public static void testContainsPerformance() { System.out.println("\n=== Contains Operations ==="); HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < TEST_SIZE; i++) { set.add(i); } // Existing elements long start = System.nanoTime(); for (int i = 0; i < 10000; i++) { set.contains(i); } long end = System.nanoTime(); System.out.printf("Contains (existing): %.2f ms%n", (end - start) / 1_000_000.0); // Non-existing elements start = System.nanoTime(); for (int i = TEST_SIZE; i < TEST_SIZE + 10000; i++) { set.contains(i); } end = System.nanoTime(); System.out.printf("Contains (non-existing): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testRemovePerformance() { System.out.println("\n=== Remove Operations ==="); HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < TEST_SIZE; i++) { set.add(i); } // Remove existing elements long start = System.nanoTime(); for (int i = 0; i < 10000; i++) { set.remove(i); } long end = System.nanoTime(); System.out.printf("Remove (existing): %.2f ms%n", (end - start) / 1_000_000.0); // Remove non-existing elements start = System.nanoTime(); for (int i = TEST_SIZE; i < TEST_SIZE + 10000; i++) { set.remove(i); } end = System.nanoTime(); System.out.printf("Remove (non-existing): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testIterationPerformance() { System.out.println("\n=== Iteration Performance ==="); HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < TEST_SIZE; i++) { set.add(i); } // Iterator iteration long start = System.nanoTime(); Iterator<Integer> iterator = set.iterator(); while (iterator.hasNext()) { iterator.next(); } long end = System.nanoTime(); System.out.printf("Iterator iteration: %.2f ms%n", (end - start) / 1_000_000.0); // For-each iteration start = System.nanoTime(); for (Integer num : set) { // Just iterating } end = System.nanoTime(); System.out.printf("For-each iteration: %.2f ms%n", (end - start) / 1_000_000.0); } public static void testMemoryUsage() { System.out.println("\n=== Memory Usage ==="); Runtime runtime = Runtime.getRuntime(); // Force garbage collection System.gc(); long memoryBefore = runtime.totalMemory() - runtime.freeMemory(); HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < TEST_SIZE; i++) { set.add(i); } long memoryAfter = runtime.totalMemory() - runtime.freeMemory(); long memoryUsed = memoryAfter - memoryBefore; System.out.printf("Memory used by HashSet with %d elements: %.2f MB%n", TEST_SIZE, memoryUsed / (1024.0 * 1024.0)); // Compare with ArrayList memoryBefore = runtime.totalMemory() - runtime.freeMemory(); ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < TEST_SIZE; i++) { list.add(i); } memoryAfter = runtime.totalMemory() - runtime.freeMemory(); long listMemoryUsed = memoryAfter - memoryBefore; System.out.printf("Memory used by ArrayList with %d elements: %.2f MB%n", TEST_SIZE, listMemoryUsed / (1024.0 * 1024.0)); } }

8. Custom Object Handling

HashSet with Custom Objects

import java.util.*; public class CustomObjectHashSet { static class Product { private String name; private int id; private double price; public Product(String name, int id, double price) { this.name = name; this.id = id; this.price = price; } // Proper hashCode implementation @Override public int hashCode() { System.out.println("hashCode() called for: " + name); return Objects.hash(name, id); } // Proper equals implementation @Override public boolean equals(Object obj) { System.out.println("equals() called for: " + name + " with " + (obj instanceof Product ? ((Product)obj).name : obj)); if (this == obj) return true; if (obj == null || getClass() != obj.getClass()) return false; Product product = (Product) obj; return id == product.id && Objects.equals(name, product.name); } @Override public String toString() { return String.format("Product{name='%s', id=%d, price=%.2f}", name, id, price); } } static class BadProduct { private String name; private int id; public BadProduct(String name, int id) { this.name = name; this.id = id; } // BAD: No hashCode override - uses Object.hashCode() // BAD: No equals override - uses Object.equals() @Override public String toString() { return String.format("BadProduct{name='%s', id=%d}", name, id); } } public static void main(String[] args) { System.out.println("=== HashSet with Custom Objects ==="); testGoodImplementation(); testBadImplementation(); testHashCodeCollisions(); } public static void testGoodImplementation() { System.out.println("\n--- Proper Implementation ---"); HashSet<Product> productSet = new HashSet<>(); Product p1 = new Product("Laptop", 1, 999.99); Product p2 = new Product("Mouse", 2, 29.99); Product p3 = new Product("Laptop", 1, 899.99); // Same name and id, different price System.out.println("Adding products:"); productSet.add(p1); productSet.add(p2); productSet.add(p3); // Should not be added (duplicate) System.out.println("Final set: " + productSet); System.out.println("Size: " + productSet.size()); } public static void testBadImplementation() { System.out.println("\n--- Bad Implementation (No hashCode/equals) ---"); HashSet<BadProduct> badSet = new HashSet<>(); BadProduct bp1 = new BadProduct("Keyboard", 1); BadProduct bp2 = new BadProduct("Keyboard", 1); // Same data System.out.println("Adding bad products:"); badSet.add(bp1); badSet.add(bp2); // Will be added even though data is same! System.out.println("Final set: " + badSet); System.out.println("Size: " + badSet.size()); System.out.println("bp1 == bp2: " + (bp1 == bp2)); System.out.println("bp1.equals(bp2): " + bp1.equals(bp2)); } public static void testHashCodeCollisions() { System.out.println("\n--- HashCode Collisions ---"); HashSet<String> collisionSet = new HashSet<>(); // Strings with same hash code String s1 = "FB"; String s2 = "Ea"; System.out.println("s1.hashCode(): " + s1.hashCode()); System.out.println("s2.hashCode(): " + s2.hashCode()); System.out.println("s1.equals(s2): " + s1.equals(s2)); collisionSet.add(s1); collisionSet.add(s2); System.out.println("Set with hash collisions: " + collisionSet); System.out.println("Size: " + collisionSet.size()); } }

9. Real-World Example

Database Result Deduplication

import java.util.*; import java.util.stream.Collectors; public class HashSetRealWorldExample { static class User { private String username; private String email; private int age; public User(String username, String email, int age) { this.username = username; this.email = email; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; return Objects.equals(username, user.username) && Objects.equals(email, user.email); } @Override public int hashCode() { return Objects.hash(username, email); } @Override public String toString() { return String.format("User{username='%s', email='%s', age=%d}", username, email, age); } } public static void main(String[] args) { System.out.println("=== Real-World Example: User Management ==="); // Simulate database results with duplicates List<User> databaseResults = Arrays.asList( new User("john_doe", "[email protected]", 25), new User("jane_smith", "[email protected]", 30), new User("john_doe", "[email protected]", 26), // Duplicate username/email new User("bob_johnson", "[email protected]", 35), new User("jane_smith", "[email protected]", 31) // Different email ); System.out.println("Raw database results (" + databaseResults.size() + "):"); databaseResults.forEach(System.out::println); // Remove duplicates using HashSet HashSet<User> uniqueUsers = new HashSet<>(databaseResults); System.out.println("\nAfter deduplication (" + uniqueUsers.size() + "):"); uniqueUsers.forEach(System.out::println); // Alternative: Using Stream distinct() List<User> distinctUsers = databaseResults.stream() .distinct() .collect(Collectors.toList()); System.out.println("\nUsing stream distinct() (" + distinctUsers.size() + "):"); distinctUsers.forEach(System.out::println); // Performance comparison performanceComparison(); } public static void performanceComparison() { System.out.println("\n=== Performance Comparison ==="); int dataSize = 100000; List<User> largeDataset = new ArrayList<>(); Random random = new Random(); // Generate dataset with duplicates for (int i = 0; i < dataSize; i++) { int id = random.nextInt(dataSize / 2); // Ensure duplicates largeDataset.add(new User("user" + id, "user" + id + "@example.com", 20 + random.nextInt(50))); } // Method 1: HashSet deduplication long start = System.nanoTime(); HashSet<User> hashSetResult = new HashSet<>(largeDataset); long hashSetTime = System.nanoTime() - start; // Method 2: Stream distinct start = System.nanoTime(); List<User> streamResult = largeDataset.stream().distinct().collect(Collectors.toList()); long streamTime = System.nanoTime() - start; System.out.printf("Dataset size: %d, Unique users: %d%n", dataSize, hashSetResult.size()); System.out.printf("HashSet deduplication: %.2f ms%n", hashSetTime / 1_000_000.0); System.out.printf("Stream distinct: %.2f ms%n", streamTime / 1_000_000.0); } }

Summary

Key Internal Mechanisms:

1. Backing HashMap: HashSet uses HashMap<E, Object> internally
2. Dummy Value: All keys map to a single PRESENT object
3. Hash Distribution: Uses HashMap's hash bucket mechanism
4. Load Factor: Default 0.75, triggers rehashing when threshold crossed
5. Fail-Fast Iterators: Detect concurrent modifications

Time Complexity (Average Case):

• add(E e): O(1)
• remove(Object o): O(1)
• contains(Object o): O(1)
• size(): O(1)
• iteration: O(n)

Important Characteristics:

1. No Duplicates: Based on equals() and hashCode()
2. Unordered: No guarantee of iteration order
3. Null Elements: Allows one null element
4. Not Thread-Safe: Requires external synchronization

Best Practices:

1. Override hashCode() and equals() for custom objects
2. Choose appropriate initial capacity if size is known
3. Use LinkedHashSet if insertion order matters
4. Consider TreeSet if sorted order is needed
5. Use Collections.synchronizedSet() for thread safety

Common Pitfalls:

1. Mutable Objects: Changing objects after adding can cause issues
2. Poor hashCode(): Can lead to performance degradation
3. No equals/hashCode: Custom objects won't work correctly
4. Concurrent modifications: Can cause ConcurrentModificationException

Understanding HashSet's internal implementation helps in writing efficient code and choosing the right collection for specific use cases.