Set Interface

Introduction

In the previous lesson, you learned about the List Interface, where elements are stored in insertion order and duplicate values are allowed.

However, many real-world applications require unique values.

For example:

• Usernames must be unique.
• Email addresses should not be duplicated.
• Product IDs must be unique.
• Employee IDs cannot repeat.
• Tags in a blogging platform should appear only once.
• Unique visitors on a website.

Using a List allows duplicates:

List<String> users = new ArrayList<>();

users.add("Rahul");
users.add("Rahul");

Output:

Rahul
Rahul

This is not desirable in many applications.

Java provides the Set Interface, which automatically prevents duplicate elements.

The Set interface is extensively used in:

• Spring Boot Applications
• Banking Systems
• E-Commerce Platforms
• Authentication Systems
• Search Engines
• Big Data Processing
• Caching Systems

In this lesson, you'll learn:

• What is Set?
• Characteristics of Set
• HashSet
• LinkedHashSet
• TreeSet
• Internal Architecture
• Hashing Mechanism
• Red-Black Tree
• Ordering
• Duplicate Detection
• Performance Analysis
• Memory Representation
• Best Practices
• Common Mistakes
• Hands-on Exercises
• Professional Interview Questions

What is Set?

A Set is a collection that stores unique elements.

Unlike List:

• No duplicate elements
• No index-based access
• Optimized for uniqueness

Example:

Set<String> fruits = new HashSet<>();

fruits.add("Apple");
fruits.add("Banana");
fruits.add("Apple");

System.out.println(fruits);

Possible Output:

Apple
Banana

The duplicate "Apple" is ignored.

Characteristics of Set

A Set:

• Stores unique elements
• Allows one null element (HashSet, LinkedHashSet)
• Does not support indexes
• Supports iteration
• Optimized for membership checks

Set Hierarchy

Iterable
    │
Collection
    │
   Set
 ┌──────┼─────────────┐
 │      │             │
HashSet LinkedHashSet TreeSet

Common Set Methods

add()

remove()

contains()

size()

isEmpty()

clear()

iterator()

Example:

Set<Integer> numbers =
        new HashSet<>();

numbers.add(10);
numbers.add(20);

System.out.println(numbers.contains(20));

Output:

true

HashSet

HashSet is the most commonly used implementation of Set.

Internally, it uses a HashMap.

Example:

Set<String> cities =
        new HashSet<>();

cities.add("Delhi");
cities.add("Mumbai");
cities.add("Hyderabad");

Internal Working of HashSet

Internally:

HashSet

↓

HashMap

↓

Hash Table

↓

Buckets

↓

Elements

Each element's hashCode() determines its bucket.

If multiple elements produce the same hash bucket, Java resolves collisions internally.

Hashing Mechanism

When adding an element:

set.add("Java");

Steps:

1. Compute hashCode()
2. Determine bucket index
3. Compare using equals()
4. If duplicate exists → Ignore
5. Else → Store element

Pseudo Flow:

Object

↓

hashCode()

↓

Bucket

↓

equals()

↓

Store / Ignore

Why equals() and hashCode() Matter

Consider a custom class:

class Employee {

    int id;

    String name;

}

If equals() and hashCode() are not overridden, two logically identical employees may both be stored in a HashSet.

Proper implementations ensure duplicate detection based on object content rather than memory references.

HashSet Memory Representation

Bucket 0

↓

Java

Bucket 1

↓

Spring

Bucket 2

↓

Hibernate

Elements are distributed across buckets based on their hash values.

HashSet Time Complexity

These are average-case complexities. Performance may degrade if many hash collisions occur.

LinkedHashSet

LinkedHashSet extends HashSet by maintaining insertion order.

Example:

Set<String> skills =
        new LinkedHashSet<>();

skills.add("Java");
skills.add("Spring");
skills.add("Kafka");

System.out.println(skills);

Output:

Java
Spring
Kafka

Internally, it combines a hash table with a linked list.

LinkedHashSet Architecture

Hash Table

↓

Linked List

↓

Maintains Insertion Order

Use LinkedHashSet when uniqueness and predictable iteration order are both required.

TreeSet

TreeSet stores unique elements in sorted order.

Internally, it uses a Red-Black Tree.

Example:

Set<Integer> marks =
        new TreeSet<>();

marks.add(80);
marks.add(95);
marks.add(70);

System.out.println(marks);

Output:

70
80
95

Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree.

Benefits:

• Sorted data
• Balanced height
• Efficient insertions
• Efficient deletions
• Efficient searches

Approximate complexity:

Search

↓

Insert

↓

Delete

↓

O(log n)

HashSet vs LinkedHashSet vs TreeSet

TreeSet Ordering

Natural ordering:

TreeSet<String> languages =
        new TreeSet<>();

languages.add("Java");
languages.add("Python");
languages.add("C");

Output:

C
Java
Python

You can also provide a custom ordering using a Comparator.

Iterating Through a Set

Using Enhanced for Loop:

for(String city : cities){

    System.out.println(city);

}

Using Iterator:

Iterator<String> iterator =
        cities.iterator();

while(iterator.hasNext()){

    System.out.println(iterator.next());

}

Real-World Example: User Registration

Set<String> usernames =
        new HashSet<>();

usernames.add("rahul");

usernames.add("amit");

usernames.add("rahul");

System.out.println(usernames);

Duplicate usernames are automatically rejected.

Real-World Example: Website Tags

Set<String> tags =
        new LinkedHashSet<>();

tags.add("Java");
tags.add("Spring");
tags.add("Microservices");

The insertion order is preserved while preventing duplicates.

Real-World Example: Leaderboard

TreeSet<Integer> scores =
        new TreeSet<>();

scores.add(250);
scores.add(180);
scores.add(300);

System.out.println(scores);

Output:

180
250
300

Best Practices

Override equals() and hashCode()

Whenever storing custom objects in a HashSet or LinkedHashSet, override both methods consistently.

Use HashSet by Default

Choose HashSet unless ordering is required.

Use LinkedHashSet for Predictable Iteration

If the order of insertion matters, prefer LinkedHashSet.

Use TreeSet for Sorted Data

When automatic sorting is required, use TreeSet.

Use Immutable Fields in Keys When Possible

Changing fields that participate in equals() or hashCode() after insertion can lead to incorrect behavior.

Common Mistakes

Expecting HashSet to Preserve Order

HashSet does not guarantee iteration order.

Forgetting equals() and hashCode()

Custom objects may appear duplicated if these methods are not implemented correctly.

Assuming TreeSet Allows Null

A TreeSet does not permit null elements because it relies on comparisons for ordering.

Modifying Objects After Insertion

Changing values that affect hashing or sorting can make elements difficult to locate.

Using TreeSet When Sorting Isn't Needed

TreeSet has higher overhead than HashSet. Use it only when sorted ordering is required.

Hands-on Exercise

Create a Java program that:

1. Creates a HashSet of employee IDs.
2. Demonstrates automatic duplicate removal.
3. Creates a LinkedHashSet of programming languages and verifies insertion order.
4. Creates a TreeSet of exam scores and displays them in sorted order.
5. Creates a custom Employee class and overrides equals() and hashCode().
6. Uses contains() to verify membership.
7. Iterates through each Set implementation using both enhanced for loops and Iterator.

Summary

The Set interface is designed for storing unique elements. HashSet offers excellent average-case performance, LinkedHashSet preserves insertion order, and TreeSet maintains sorted order using a Red-Black Tree. Choosing the correct implementation depends on whether uniqueness, ordering, or sorting is the primary requirement.

Key Takeaways

• Set stores unique elements.
• HashSet uses hashing for fast average-case operations.
• LinkedHashSet preserves insertion order.
• TreeSet stores elements in sorted order.
• TreeSet is backed by a Red-Black Tree.
• equals() and hashCode() are essential for custom objects in hash-based sets.
• TreeSet relies on natural ordering or a Comparator.
• Choose the Set implementation based on ordering and performance requirements.

Professional Interview Questions