Sets and Hash Sets

# CHAPTER 17

Sets and Hash Sets #

1. Introduction #

2. Learning Objectives #

• Define the architectural purpose of a Set.

• Understand the relationship between a Hash Map and a Hash Set.

• Perform core Set operations (Union, Intersection, Difference).

• Utilize Hash Sets to brutally optimize coding interview algorithms.

3. The Core Concept: Uniqueness #

4. How is a HashSet Built? #

When you insert the email "john@gmail.com":

1. 1. The string runs through the exact same O(1) Hash Function.

1. 2. It generates an array index (e.g., [4]).

1. 3. It drops the string into index [4].

1. 4. If "john@gmail.com" is inserted again, the Hash Function generates [4] again. The system sees data is already there, confirms it matches, and silently rejects the insertion.

Result: O(1) Insertions, O(1) Duplicate Checking!

5. Implementation in Modern Languages #

# Python Example: Built-in Set
# Sets use curly braces, just like dictionaries, but without the colon ':'
unique_emails = {"alice@gmail.com", "bob@yahoo.com"}

# O(1) Insertion
unique_emails.add("charlie@gmail.com")
unique_emails.add("alice@gmail.com") # Ignored! Duplicate!

# O(1) Fast Lookup (The 'in' keyword)
if "bob@yahoo.com" in unique_emails:
    print("Bob is already registered!")

print(unique_emails) 
# Notice the output is entirely scrambled! Sets are NOT ordered.

// Java Example: HashSet
import java.util.HashSet;

public class SetExample {
    public static void main(String[] args) {
        HashSet<Integer> numbers = new HashSet<>();

        numbers.add(10);
        numbers.add(20);
        numbers.add(10); // Ignored silently

        // Instant O(1) check
        if (numbers.contains(20)) {
            System.out.println("20 exists in the Set.");
        }
    }
}

6. Mathematical Set Operations #

Given Set A = {1, 2, 3} and Set B = {3, 4, 5}:

• Union (A | B): Combines both. {1, 2, 3, 4, 5}.

• Intersection (A & B): Returns only the elements present in BOTH sets. {3}.

• Difference (A - B): Returns elements in A that are NOT in B. {1, 2}.

# Python Example: Set Operations
group1 = {"Alice", "Bob", "Charlie"}
group2 = {"Charlie", "David", "Eve"}

# Who is in BOTH groups? (Intersection)
common_members = group1.intersection(group2)
print(common_members) # Output: {'Charlie'}

7. Real-World Applications #

1. 1. Duplicate Filtering: Taking an array of 1 million dirty records, dumping it into a Set, and converting it back to an array to instantly wipe all duplicates.

1. 2. Social Media Connections: Finding "Mutual Friends". If you are Set A and your friend is Set B, a mathematical Intersection instantly yields your mutual friends!

1. 3. Spell Checkers: Storing 500,000 valid English words in a Hash Set. As you type, the software does an O(1) contains() check on every word. If it returns False, a red squiggly line appears.

8. Mini Project: Array Duplicate Filter #

// Java: O(n) Duplicate Removal utilizing a HashSet
import java.util.*;

public class DuplicateFilter {
    public static void main(String[] args) {
        int[] rawData = {5, 9, 2, 5, 1, 9, 5, 3};
        
        // 1. Initialize Set
        HashSet<Integer> cleanSet = new HashSet<>();
        
        // 2. Loop through array O(n)
        for (int num : rawData) {
            cleanSet.add(num); // Duplicates are instantly rejected!
        }
        
        // Output the perfectly clean, unique data
        System.out.println(cleanSet); // Output: [1, 2, 3, 5, 9] (Order not guaranteed)
    }
}

9. Common Mistakes #

• Assuming Sets are Ordered: Because Hash Sets use the chaotic Hash Function, the internal array indexes are entirely scrambled. If you insert 1, 2, 3, it might print 3, 1, 2. If you absolutely require a Set that remembers the order of insertion, you must use a specialized structure like Java's LinkedHashSet.

10. Best Practices #

• FAANG Interview Secret Weapon: In any technical interview, if a problem asks you to "find duplicates", "find unique elements", or "check if an element exists quickly", your brain should instantly scream: "HASH SET!". Converting an O(n²) nested loop into an O(n) Set lookup is the easiest way to impress an interviewer.

11. Exercises #

1. 1. Write a function that takes two arrays of integers and returns a new array containing only the numbers that exist in BOTH arrays in O(n) time.

1. 2. Why does checking if item in list: take O(n) in Python, but if item in set: takes O(1)?

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Given a massive string of text, write an algorithm to find the length of the longest substring without repeating characters." *(Answer: The famous FAANG 'Sliding Window' problem. Use two pointers to create a window, and a HashSet to instantly check if the newest character entering the window is a duplicate!).*

Common Pitfalls:

• Forgetting the Space Complexity tradeoff! Yes, dumping an array into a Set reduces Time Complexity from O(n²) to O(n). However, it requires allocating a completely new data structure in RAM, resulting in an O(n) Space Complexity overhead! Always mention this tradeoff to the interviewer.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #