Set / HashSet

🎯 Goal: Understand what a Set is, why it’s useful, and how to build a custom HashSet in Java from scratch.

📝 Table of Contents

1. What is a Set?
2. Usage of Sets
3. Built-in Java HashSet
4. Implementing Custom HashSet
5. Time and Space Complexity
6. Summary

1️⃣ What is a Set?

In computer science, a Set is an abstract data structure that stores unique elements, without any particular order.

It mainly supports three operations:

• add(): Adds an element to the set.
• remove(): Removes an element from the set.
• contains(): Checks if an element exists in the set.

2️⃣ Usage of Sets

• Uniqueness: Ensures that only unique elements exist in a collection.
• Fast Lookup: Offers fast O(1) lookup times (ideally).
• Mathematical Operations: Can perform mathematical set operations like union, intersection, etc.

3️⃣ Built-in Java HashSet

Java has a built-in HashSet class that can be used like this:

HashSet<Integer> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(1);  // won't get added
System.out.println(mySet.contains(1));  // returns true

4️⃣ Implementing Custom HashSet

Let’s implement a simple CustomHashSet using an array of linked lists (for handling collisions).

public class CustomHashSet {
    
    private LinkedList<Integer>[] container;
    private static final int SIZE = 1000;

    public CustomHashSet() {
        container = new LinkedList[SIZE];
    }

    public void add(int key) {
        int index = getIndex(key);
        if (container[index] == null) {
            container[index] = new LinkedList<>();
        }
        if (!container[index].contains(key)) {
            container[index].addFirst(key);
        }
    }

    public void remove(int key) {
        int index = getIndex(key);
        if (container[index] != null) {
            container[index].remove((Integer) key);
        }
    }

    public boolean contains(int key) {
        int index = getIndex(key);
        return (container[index] != null && container[index].contains(key));
    }

    private int getIndex(int key) {
        return key % SIZE;
    }
}

5️⃣ Time and Space Complexity

• Time Complexity: Ideally, each operation in a HashSet runs in O(1) time.
• Space Complexity: O(N) where N is the number of elements stored.

6️⃣ Summary

A Set is a useful data structure for maintaining a collection of unique elements. Java provides a built-in HashSet, but knowing how to implement your custom HashSet is a great exercise to understand hashing and collision resolution.