Sets (Aashray)

Java Sets: In-Depth Overview

What Is a Set?

A Set is a collection that stores unique elements. Unlike lists, sets do not allow duplicate values. While the typical Set does not guarantee any ordering of elements, some implementations offer sorted or insertion-ordered behaviors. The key characteristics of a set are:

  • No Duplicates: Every element in a set is unique.
  • No Guaranteed Order: The standard Set (such as HashSet) does not maintain the order of its elements. However, specialized implementations like LinkedHashSet and TreeSet provide predictable ordering (insertion order and natural sorted order, respectively).

Types of Sets in Java

  1. HashSet
    • Description: The most commonly used set implementation; it uses a hash table for storage.
    • Ordering: Does not maintain any order.
    • Performance: Offers constant-time performance for basic operations (add, remove, contains) if the hash function disperses the elements properly.
    • Limitations: No duplicate elements; order is unpredictable.
  2. LinkedHashSet
    • Description: Extends HashSet and maintains a linked list of the entries.
    • Ordering: Preserves the order of insertion.
    • Use Case: Useful when iteration order matters while still enforcing uniqueness.
  3. TreeSet
    • Description: Implements the SortedSet interface using a red-black tree structure.
    • Ordering: Automatically sorts the elements in their natural order (or according to a custom Comparator).
    • Use Case: Ideal for applications where a sorted set is required.
    • Performance: Provides logarithmic time cost for basic operations.
  4. EnumSet
    • Description: A specialized set implementation designed exclusively for use with enum types.
    • Ordering: The iteration order is the natural order of the enum values.
    • Benefits: Very efficient in both time and space for enum types.

Common Operations on Sets

  • Add Elements
    • boolean add(E e): Adds the specified element to the set if it is not already present.
  • Remove Elements
    • boolean remove(Object o): Removes the specified element from the set if it is present.
  • Check for an Element
    • boolean contains(Object o): Returns true if the set contains the specified element.
  • Size and Emptiness
    • int size(): Returns the number of elements in the set.
    • boolean isEmpty(): Returns true if the set contains no elements.
  • Iteration
    • Iterator<E> iterator(): Returns an iterator over the set’s elements. You can use this with an enhanced for loop (for-each loop).
  • Bulk Operations
    • boolean addAll(Collection<? extends E> c): Adds all elements from the specified collection.
    • boolean removeAll(Collection<?> c): Removes from the set all of its elements that are contained in the specified collection.
    • boolean retainAll(Collection<?> c): Retains only the elements in the set that are contained in the specified collection.

What You Can and Cannot Do with Sets

You Can:

  • Store Unique Elements: Automatically ignore any duplicate values.
  • Perform Fast Lookups: Particularly with implementations like HashSet, operations such as add and contains are typically very fast.
  • Use Specialized Sets: For example, using TreeSet for a sorted collection or LinkedHashSet to maintain insertion order.
  • Bulk Operations: Easily combine, remove, or retain collections of elements using methods like addAll(), removeAll(), and retainAll().

You Cannot:

  • Store Duplicates: Sets inherently reject duplicate items.
  • Access by Index: Since sets do not maintain a positional order (except when using a List), you cannot retrieve an element by its index using methods like get(int index).
  • Assume a Specific Order: With standard sets (e.g., HashSet), the iteration order is not predictable. Use LinkedHashSet or TreeSet when order is important.

Mini Example: Iterating Over a HashSet

Below is a small Java program that demonstrates how to use a HashSet, including adding elements, attempting to add duplicates, and iterating over the set:

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        // Create a HashSet of strings
        Set<String> colors = new HashSet<>();

        // Adding elements to the set
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");

        // Attempt to add a duplicate element
        boolean added = colors.add("Red"); // This will return false

        System.out.println("Was 'Red' added again? " + added); // Outputs: false

        // Common Operations:
        // Check if the set contains "Green"
        if (colors.contains("Green")) {
            System.out.println("The set contains Green.");
        }

        // Get the size of the set
        System.out.println("The set has " + colors.size() + " elements.");

        // Iterating over the set using an enhanced for-loop
        System.out.println("Colors in the set:");
        for (String color : colors) {
            System.out.println(color);
        }
    }
}

SetExample.main(null);

Was 'Red' added again? false
The set contains Green.
The set has 3 elements.
Colors in the set:
Red
Blue
Green

// Create a HashSet to store unique numbers:

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(5); // Duplicate, will be ignored.
        numbers.add(7);
        
        System.out.println("Unique numbers: " + numbers);
    }
}

HashSetDemo.main(null);

Unique numbers: [3, 5, 7]

// Create a HashMap to map student IDs to names:

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<Integer, String> studentMap = new HashMap<>();
        studentMap.put(101, "Alice");
        studentMap.put(102, "Bob");
        studentMap.put(103, "Charlie");

        // Retrieve value by key
        System.out.println("Student 102: " + studentMap.get(102));

        // Iterate using keySet()
        System.out.println("Student Roster:");
        for (Integer id : studentMap.keySet()) {
            System.out.println("ID: " + id + ", Name: " + studentMap.get(id));
        }
    }
}

HashMapDemo.main(null);

Student 102: Bob
Student Roster:
ID: 101, Name: Alice
ID: 102, Name: Bob
ID: 103, Name: Charlie

POPCORN HACK

Task: Create a HashMap that stores names as keys and phone numbers (as strings) as values.

  1. Add at least 5 entries.
  2. Implement a simple search method that prompts the user (using Scanner) to enter a name and then prints out the corresponding phone number (or a “not found” message).

Optional:

  • Allow the user to perform multiple lookups (looping until the user enters a quit command).
  • Implement a method to print the entire phone book in a sorted order (by key).
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class PhoneBook {
    public static void main(String[] args) {
        // code
    }
}

PhoneBook.main(null);

Takeaways:

  • No Duplicates: Duplicate items are rejected (as seen when "Red" is not added twice).
  • No Order Guarantee: The order in which colors are printed may vary from the insertion order.
  • Basic Operations: Methods such as add(), contains(), size(), and iteration using the enhanced for-loop provide a simple interface for working with sets.